Combinations (n choose k)

Medium TimeO(k · C(n, k)) SpaceO(n)

A combination is a selection where order does not matter, so choosing 1 then 2 is the same as choosing 2 then 1 and must appear only once. Given n and k, return every way to choose k numbers from 1 to n. Each number may be chosen at most once, and there are exactly n-choose-k results.

Examples

Example 1

Input
n = 4k = 2
Output
[[3,4],[2,4],[1,4],[2,3],[1,3],[1,2]]
Six ways to pick 2 of 4: 4 × 3 ÷ 2, the division removing each pair's mirror image.

Example 2

Input
n = 3k = 3
Output
[[1,2,3]]
Choosing all three leaves nothing to decide, so there is exactly one way.

The Code

function combine(n, k) {
  if (k === 0) return [[]];
  if (n < k) return [];
  const withN = combine(n - 1, k - 1).map((c) => [...c, n]);
  const withoutN = combine(n - 1, k);
  return [...withN, ...withoutN];
}
combine(4, 2);
Done
Step through combine(4, 2) call by call

More like this

All backtracking examples (10) →