Combinations

medium backtracking combinations

Problem

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order.

Recurse with the next allowed start. At each level, iterate i = start..n, append i, recurse with start i + 1, then pop. Pruning: stop the loop early when the remaining numbers cannot fill the remaining slots, i.e. when i > n - (k - len) + 1.

Inputn = 4, k = 2

Output[1,2] [1,3] [1,4] [2,3] [2,4] [3,4]

Six combinations — C(4,2). Order within a tuple is increasing; the recursion guarantees this.

def combine(n, k):
    out, path = [], []
    def back(start):
        if len(path) == k:
            out.append(path.copy()); return
        end = n - (k - len(path)) + 1
        for i in range(start, end + 1):
            path.append(i)
            back(i + 1)
            path.pop()
    back(1)
    return out

function combine(n, k) {
  const out = [], path = [];
  function back(start) {
    if (path.length === k) { out.push(path.slice()); return; }
    const end = n - (k - path.length) + 1;
    for (let i = start; i <= end; i++) {
      path.push(i);
      back(i + 1);
      path.pop();
    }
  }
  back(1);
  return out;
}

List<List<Integer>> out = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
    back(1, n, k);
    return out;
}
void back(int start, int n, int k) {
    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }
    int end = n - (k - path.size()) + 1;
    for (int i = start; i <= end; i++) {
        path.add(i);
        back(i + 1, n, k);
        path.remove(path.size() - 1);
    }
}

vector<vector<int>> out;
vector<int> path;
void back(int start, int n, int k) {
    if ((int)path.size() == k) { out.push_back(path); return; }
    int end = n - (k - (int)path.size()) + 1;
    for (int i = start; i <= end; i++) {
        path.push_back(i);
        back(i + 1, n, k);
        path.pop_back();
    }
}
vector<vector<int>> combine(int n, int k) {
    back(1, n, k);
    return out;
}

Explanation

We need every way to choose k numbers out of 1..n. To avoid generating the same set in different orders, we always build combinations in increasing order.

The function back(start) appends numbers starting from start. After choosing i, it recurses with i + 1 so the next pick is strictly larger. When path reaches length k, it's a complete combination and gets saved; then we pop and try the next candidate.

The clever part is the pruning bound end = n - (k - len(path)) + 1. It says: if we still need k - len(path) more numbers, the loop can't start past this point, because there wouldn't be enough numbers left to fill all the remaining slots. Skipping those doomed branches makes the search much tighter.

Example: n = 4, k = 2. We pick 1, then 2,3,4 → [1,2],[1,3],[1,4]; pick 2 → [2,3],[2,4]; pick 3 → [3,4]. Starting at 4 is pruned because one number can't fill two slots. That gives the six expected combinations.

Because we only ever move forward and prune impossible starts, every combination is produced exactly once and in sorted form.

Time: O(C(n, k) · k) Space: O(k) recursion