Combinations

The problem. Given two integers n and k, return all possible combinations of k numbers chosen from 1 to n, in any order.

Example

n = 4, k = 2  ->  [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
n = 1, k = 1  ->  [[1]]

The idea: a start index keeps one order

A combination is a set, so [1, 2] and [2, 1] are the same. Building each combination in increasing order makes every set appear exactly once: after choosing x, only try numbers bigger than x. That's the start parameter. And there's a cheap but powerful prune: if the path still needs k − path.length more numbers, the next choice can be at most n − (k − path.length) + 1 — anything bigger leaves too few numbers to finish.

1. Backtracking from a start index

1function combine(n, k) {2  const result = [];3  const path = [];4  const build = (start) => {5    if (path.length === k) {6      result.push([...path]);7      return;8    }9    for (let x = start; x <= n; x++) {       // only numbers bigger than the last one10      path.push(x);11      build(x + 1);12      path.pop();13    }14  };15  build(1);16  return result;17}

Time O(C(n, k) · k) plus dead branches that run out of numbers, space O(k).

2. The same, with pruning

1function combine(n, k) {2  const result = [];3  const path = [];4  const build = (start) => {5    if (path.length === k) {6      result.push([...path]);7      return;8    }9    const last = n - (k - path.length) + 1;    // beyond this, too few numbers are left10    for (let x = start; x <= last; x++) {11      path.push(x);12      build(x + 1);13      path.pop();14    }15  };16  build(1);17  return result;18}

Time O(C(n, k) · k), space O(k). Every branch now reaches a real combination, so no work is wasted — a big saving when k is close to n.

Comparing the approaches

Edge cases to test

Variations