LeetCode Subsets I & II：子集生成的回溯與去重模板

Subsets I：無重複元素集合的所有子集

對目標子集大小 k = 0..n，DFS 組合生成。標準回溯模板：

void dfs(int[] nums, int start, int k, List path, List> res) {
    if (path.size() == k) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        dfs(nums, i+1, k, path, res);
        path.remove(path.size()-1);
    }
}
// 主函數：排序後對 k=0..n 循環調用 dfs

Subsets II：含重複元素，子集不重複

關鍵：同層遞歸中跳過相同元素。排序後，在 for 循環中：

int i = start;
while (i < nums.length) {
    path.add(nums[i]);
    dfs(nums, i+1, k, path, res);
    path.remove(path.size()-1);
    // 跳過所有相同的 nums[i]
    while (i+1 < nums.length && nums[i] == nums[i+1]) i++;
    i++;
}

這樣對於 [1,1,2]，生成 [1,2] 時只會用第一個 1 進入遞歸，第二個 1 在同層被跳過，避免重複子集。

複雜度

• 時間：O(n × 2ⁿ) —— 輸出敏感，每個子集複製 O(n)。
• 空間：O(n) 遞歸棧 + O(n × 2ⁿ) 結果存儲。

Java 完整類

public class Solution {
    public List> subsets(int[] S) { ... } // I
    public List> subsetsWithDup(int[] num) { ... } // II
}