Combinations / choose K (Backtracking Sub-pattern)

// Choose K: pick items in increasing order (start index), so each group appears once.
// Prune when the numbers left can't fill the remaining slots.
void build(int n, int k, int start, vector<int>& path, vector<vector<int>>& out) {
    if ((int)path.size() == k) { out.push_back(path); return; }
    int need = k - path.size();
    for (int i = start; i <= n - need + 1; i++) {        // i > n-need+1 leaves too few numbers
        path.push_back(i);
        build(n, k, i + 1, path, out);                   // next pick must be larger
        path.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> out;
    vector<int> path;
    build(n, k, 1, path, out);
    return out;
}