Combinations via Backtracking

A combination chooses k items from n where order does not matter. There are C(n,k) = n! / (k! · (n-k)!) such selections. Backtracking generates them by always picking from the remaining elements (never going back), which naturally eliminates duplicates caused by reordering.

Basic Backtracking Implementation

function combinations(nums, k) {
  const result = [];

  function backtrack(start, current) {
    // Base case: selected exactly k elements
    if (current.length === k) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);        // choose
      backtrack(i + 1, current);    // explore (i+1 avoids reuse)
      current.pop();                // undo
    }
  }

  backtrack(0, []);
  return result;
}

console.log(combinations([1, 2, 3, 4], 2));
// [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Passing i + 1 (not start + 1) to the recursive call ensures each element is used at most once and elements are always chosen in forward order, preventing [2,1] from appearing alongside [1,2].

Pruning by Remaining Slots

Even before reaching the base case you can detect dead ends: if the number of remaining elements in nums is fewer than the spots still needed in current, no valid combination can be completed from this branch:

function combinationsPruned(nums, k) {
  const result = [];

  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }

    const needed = k - current.length;        // how many more we need
    const available = nums.length - start;    // how many are left

    // Prune: not enough elements remaining
    if (available < needed) return;

    for (let i = start; i <= nums.length - needed; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return result;
}

The upper bound i <= nums.length - needed tightens the loop range, skipping iterations that can never complete a valid combination.

Complexity

The time cost is C(n,k) · k: there are C(n,k) leaf nodes and each requires O(k) work to copy the current selection. The call stack depth is at most k, giving O(k) space (excluding output).

Combinations are significantly cheaper than permutations for large n when k is small, because order does not matter and the pruning cuts many branches early.

Up Next

Subsets generalize combinations to every possible value of k simultaneously — and a bitmask trick generates all 2^n subsets without any recursion at all.