Combinations

4 snippets across 3 stacks — Interview Prep, Python, SQL

Also written as all combinations

DSAInterview Prep

Combinations

syntax

Choose k items from n without regard to order.
Backtrack: at each step, choose to include or exclude the current element.
Only pick elements with index >= start to avoid duplicates.

example

// JavaScript
function combine(n, k) {
  const result = [];
  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    for (let i = start; i <= n; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(1, []);
  return result;
}

# Python
def combine(n, k):
    result = []
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    backtrack(1, [])
    return result

output

combine(4, 2) → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Note Time O(C(n,k) * k), Space O(k) for recursion depth. The key difference from permutations: use a 'start' parameter to only pick forward, preventing duplicate combinations. Optimization: prune when remaining elements < needed elements (n - i + 1 < k - len(current)).

Subsets (Power Set)

DSA · Recursion & Backtracking

syntax

Generate all 2^n subsets of a set.
Backtrack: for each element, choose to include it or not.
Alternative: iterative bit manipulation.

example

// JavaScript
function subsets(nums) {
  const result = [];
  function backtrack(start, current) {
    result.push([...current]); // every state is a valid subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(0, []);
  return result;
}

// Iterative approach
function subsetsIterative(nums) {
  const result = [[]];
  for (const num of nums) {
    const newSubsets = result.map(sub => [...sub, num]);
    result.push(...newSubsets);
  }
  return result;
}

# Python
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

output

subsets([1,2,3]) → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

Note Time O(2^n * n), Space O(n) recursion depth. Unlike combinations, we add to result at every recursive call (not just when a condition is met). For subsets with duplicates: sort the input, then skip nums[i] == nums[i-1] when i > start. The iterative approach is elegant and avoids recursion.

PYPython

itertools Highlights

PY · Comprehensions & Generators

syntax

import itertools

example

from itertools import chain, islice, groupby, product

# Chain multiple iterables
all_items = list(chain([1, 2], [3, 4], [5]))
print(all_items)

# Take first N from any iterable
first_three = list(islice(range(1000000), 3))
print(first_three)

# Cartesian product
sizes = ["S", "M"]
colors = ["red", "blue"]
combos = list(product(sizes, colors))
print(combos)

output

[1, 2, 3, 4, 5]
[1, 2, 3]
[('S', 'red'), ('S', 'blue'), ('M', 'red'), ('M', 'blue')]

Note itertools functions return lazy iterators. They compose well and avoid creating intermediate lists. See also: accumulate, starmap, tee, zip_longest.

SQLSQL

CROSS JOIN

SQL · Joins

syntax

SELECT columns
FROM table1
CROSS JOIN table2;

example

SELECT s.size_name, c.color_name
FROM sizes s
CROSS JOIN colors c;

output

-- Every combination of size and color
-- If 4 sizes and 5 colors, result has 20 rows

Note CROSS JOIN produces the Cartesian product — every row in table1 paired with every row in table2. Row count = rows_in_A * rows_in_B, so it can explode quickly on large tables.