LeetCode 77 組合生成：回溯法標準模板與剪枝優化

問題描述

給定 n, k，返回 [1..n] 中所有大小為 k 的組合。如 n=4, k=2 → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。

回溯框架

vector> combine(int n, int k) {
    vector> res;
    vector path;
    function dfs = [&](int start) {
        if (path.size() == k) { res.push_back(path); return; }
        for (int i = start; i <= n - (k - path.size()) + 1; ++i) { // 剪枝
            path.push_back(i);
            dfs(i + 1);
            path.pop_back();
        }
    };
    dfs(1);
    return res;
}

剪枝條件詳解

剩餘可選數字個數 n - i + 1 必須 ≥ 還需選擇個數 k - path.size()。
即 i ≤ n - (k - path.size()) + 1。這能大幅減少遞歸調用。

迭代實現（非遞歸）

vector> combine(int n, int k) {
    vector> res;
    vector comb(k, 0);
    int idx = 0;
    while (idx >= 0) {
        if (++comb[idx] > n - k + 1 + idx) { --idx; continue; }
        if (idx == k - 1) res.push_back(comb);
        else comb[++idx] = comb[idx-1];
    }
    return res;
}

複雜度

時間 O(C(n,k) * k)（生成每個組合需 O(k) 拷貝），空間 O(k) 遞歸棧 + O(C(n,k)*k) 結果存儲。

擴展：組合總和、子集等同構問題

同樣框架適用於 LeetCode 39/40/78/90 等，只需修改剪枝條件與終止判斷。