Pick k elements where order doesn't matter. A start index enforces increasing picks so [1,2] and [2,1] aren't counted twice. Prune when too few elements remain to finish.
Recurse with a start value and only pick elements at index ≥ start. This forces every combination to be strictly increasing, killing the order-duplicates that plague permutations.
k - path.size() more elementsn - i + 1 remain from index ipath.size() == kvoid dfs(int start, int n, int k,
vector<int>& path, vector<vector<int>>& out) {
if (path.size() == k) { // picked enough
out.push_back(path);
return;
}
// prune: not enough numbers left to reach size k
int need = k - path.size();
for (int i = start; i <= n - need + 1; i++) {
path.push_back(i); // CHOOSE i
dfs(i + 1, n, k, path, out); // next starts after i
path.pop_back(); // UNCHOOSE
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> out;
vector<int> path;
dfs(1, n, k, path, out);
return out; // C(n, k) combinations
}One length-k copy per combination generated.
Recursion depth is capped at k, plus the working path.
n! / (k!·(n-k)!), order-independent selections.
i+1 forward means each element can only be followed by larger ones, so sets never repeat in a different order.i <= n - need + 1 is the prune baked into the range, it never even enters doomed branches.i, not i+1).