LeetCode Combinations：DFS 生成所有組合

題目

給定整數 n 和 k，返回從 1..n 中選取 k 個數的所有組合（順序無關）。

例：n=4, k=2 → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。

DFS/回溯算法

• 遞歸函數 dfs(level, start, path)：
• level：已選數字個數
• start：下一可選數字（保證遞增，避免重複）
• path：當前組合
• 終止條件：level == k → 加入結果集
• 循環 i = start .. n：選 i，遞歸 dfs(level+1, i+1, path+{i})，回溯彈出

Java 實現

import java.util.*;

public class Combinations {
    private List> res = new ArrayList<>();
    private int n, k;

    public List> combine(int n, int k) {
        this.n = n; this.k = k;
        dfs(0, 1, new ArrayList<>());
        return res;
    }

    private void dfs(int level, int start, List path) {
        if (level == k) {
            res.add(new ArrayList<>(path)); // 拷貝快照
            return;
        }
        for (int i = start; i <= n; ++i) {
            path.add(i);
            dfs(level + 1, i + 1, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

關鍵點

• start = i+1 保證組合內遞增，天然去重。
• 結果集存入時 必須拷貝 new ArrayList<>(path)，否則後續回溯會修改已存列表。
• 剪枝優化：若剩餘數字不足填滿 k，可提前返回。
  if (n - i + 1 < k - level) break;

複雜度

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

迭代版（非遞歸）

public List> combine(int n, int k) {
    List> res = new ArrayList<>();
    int[] comb = new int[k];
    for (int i = 0; i < k; ++i) comb[i] = i + 1; // 初始 [1,2,..,k]

    while (true) {
        res.add(Arrays.stream(comb).boxed().collect(Collectors.toList()));
        // 找最右可增位
        int i = k - 1;
        while (i >= 0 && comb[i] == n - k + i + 1) --i;
        if (i < 0) break;
        ++comb[i];
        for (int j = i + 1; j < k; ++j) comb[j] = comb[j-1] + 1;
    }
    return res;
}

迭代版無遞歸開銷，適合棧深度受限環境。