Combinations

Overview

A combination is a selection of k items where order does not matter: {1, 2} and {2, 1} are the same combination. There are C(n, k) = n! / (k! (n - k)!) of them. Backtracking generates combinations by always picking the next element from a start index onward, which guarantees each selection appears in exactly one order.

Combination problems usually add constraints: a target sum, a fixed size, allowed reuse, or restricted digits. The start index controls whether items can be reused (recurse with i) or not (recurse with i + 1).

When to use it

• Choose k items out of n, order irrelevant.
• Find all groups that reach a target sum.
• Generate teams, committees, or feature subsets of a fixed size.
• Count combinations with Pascal's triangle or the formula.

Problem patterns it solves

Where it is used in real software

Key terms

C(n, k)

Number of ways to choose k items from n: n! / (k! (n - k)!).

Start index

The first index allowed at the current level, preventing reordered duplicates.

Pascal's rule

C(n, k) = C(n - 1, k - 1) + C(n - 1, k).

Pruning by remaining slots

Stop if fewer elements remain than slots still needed.

How it works, step by step

1. 1
   Recurse with a start index

   backtrack(start, path).

2. 2
   Record when full

   If path.length === k (or remaining target is 0), save a copy.

3. 3
   Loop from start

   Try each i >= start as the next chosen element.

4. 4
   Prune

   If n - i < k - path.length, not enough elements remain: stop.

5. 5
   Recurse with i + 1

   Use i instead if reuse is allowed.

C(4, 2): combinations of [1, 2, 3, 4] of size 2

start index ensures increasing order inside each combination

6 combinations, matching C(4, 2) = 4! / (2! x 2!) = 6. Starting at 4 is pruned because no elements remain for the second slot.

Implementation

1function combine(n, k) {2  const result = [], path = [];3  function backtrack(start) {4    if (path.length === k) {5      result.push([...path]);6      return;7    }8    const need = k - path.length;9    for (let i = start; i <= n - need + 1; i++) { // prune: leave room for the rest10      path.push(i);11      backtrack(i + 1);12      path.pop();13    }14  }15  backtrack(1);16  return result;17}18 19// 216. Combination Sum III: k numbers from 1..9 summing to n20function combinationSum3(k, n) {21  const result = [], path = [];22  function backtrack(start, remaining) {23    if (path.length === k) {24      if (remaining === 0) result.push([...path]);25      return;26    }27    for (let d = start; d <= 9 && d <= remaining; d++) {28      path.push(d);29      backtrack(d + 1, remaining - d);30      path.pop();31    }32  }33  backtrack(1, n);34  return result;35}36 37// C(n, k) without overflow for moderate values38function nCk(n, k) {39  k = Math.min(k, n - k);40  let result = 1;41  for (let i = 1; i <= k; i++) result = (result * (n - k + i)) / i; // stays an integer42  return result;43}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Restarting the loop at 0.

  Fix: That produces permutations of the same combination; always loop from start.

• Computing n! directly.

  Fix: Factorials overflow quickly; use the multiplicative formula or Pascal's triangle.

Interview questions

Practice problems