LeetCode Combinations：組合生成遞歸回溯標準解法

題目

給定 n、k，返回 [1..n] 中所有大小為 k 的組合。順序不重要。

遞歸回溯

函數 backtrack(start, path)：若 path.size()==k 加入結果。否則從 start 到 n 遍歷，加入 path，遞歸 i+1，回溯移除。

完整 Java 代碼

class Solution {
    public List> combine(int n, int k) {
        List> res = new ArrayList<>();
        backtrack(n, k, 1, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int n, int k, int start, List path, List> res) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; ++i) {
            path.add(i);
            backtrack(n, k, i+1, path, res);
            path.remove(path.size()-1);
        }
    }
}

剪枝優化

若剩餘數字不足填滿 k，提前返回：

if (path.size() + (n - start + 1) < k) return;

複雜度

時間 O(C(n,k) * k)，空間 O(C(n,k) * k) 存結果，遞歸棧 O(k)。