LeetCode Combinations：回溯算法生成組合

問題描述

給定整數 n 和 k，返回 [1, n] 中選取 k 個數的所有組合。順序不限。
示例：n=4, k=2 → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。

回溯算法

• 遞歸函數 backtrack(start, path)：start 為下一可選數字，path 為當前組合。
• 若 path.size() == k，加入結果集返回。
• 從 start 到 n 循環：選 i，加入 path，遞歸 backtrack(i+1, path)，回溯彈出 i。

代碼實現

class Solution {
public:
    vector> combine(int n, int k) {
        vector> res;
        vector path;
        backtrack(n, k, 1, path, res);
        return res;
    }
private:
    void backtrack(int n, int k, int start, vector& path, vector>& res) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        // 剪枝：剩餘數字不足填滿 path
        if (n - start + 1 < k - (int)path.size()) return;
        for (int i = start; i <= n; ++i) {
            path.push_back(i);
            backtrack(n, k, i + 1, path, res);
            path.pop_back();
        }
    }
};

複雜度

時間 O(C(n,k) * k)，空間 O(k) 遞歸棧 + 結果集。C(n,k) 為組合數。

迭代實現（非遞歸）

vector> combine(int n, int k) {
    vector> res;
    vector comb(k);
    iota(comb.begin(), comb.end(), 1);  // 1,2,...,k
    while (true) {
        res.push_back(comb);
        int i = k - 1;
        while (i >= 0 && comb[i] == n - k + 1 + i) --i;
        if (i < 0) break;
        ++comb[i];
        for (int j = i + 1; j < k; ++j) comb[j] = comb[j-1] + 1;
    }
    return res;
}

字典序生成下一組合，無遞歸開銷。