子集 II 图解题解

这道题到底在问什么

nums

[1,2,2]

输出

[[],[1],[1,2],[1,2,2],[2],[2,2]]

最优解：一步一步想明白

1. 3记住这句，下面每一步都在套它。
2. 4根节点：空路径也是一个合法子集 → 收集 []。
3. 5这一层从下标 0 的 1 往下钻：把它加进 path。
4. 6path → [1]，进入下一层(从下标 1 继续，避免重复用同一个位置)。
5. 7每到一个节点先把当前 path 收进结果：[1]。
6. 8这一层从下标 1 的 2 往下钻：把它加进 path。
7. 9path → [1,2]，进入下一层(从下标 2 继续，避免重复用同一个位置)。
8. 10每到一个节点先把当前 path 收进结果：[1,2]。
9. 11这一层从下标 2 的 2 往下钻：把它加进 path。
10. 12path → [1,2,2]，进入下一层(从下标 3 继续，避免重复用同一个位置)。
11. 13每到一个节点先把当前 path 收进结果：[1,2,2]。
12. 14这条分支走完，撤销 2（path → [1,2]），回到上一层换下一个候选。
13. 15这条分支走完，撤销 2（path → [1]），回到上一层换下一个候选。
14. 16下标 2 的 2 和同层前一个下标 1 的 2 相同，这一层已经从 2 开过分支了，再选会产生重复子集 → 画 ✗ 剪掉。
15. 17这条分支走完，撤销 1（path → []），回到上一层换下一个候选。
16. 18这一层从下标 1 的 2 往下钻：把它加进 path。
17. 19path → [2]，进入下一层(从下标 2 继续，避免重复用同一个位置)。
18. 20每到一个节点先把当前 path 收进结果：[2]。
19. 21这一层从下标 2 的 2 往下钻：把它加进 path。
20. 22path → [2,2]，进入下一层(从下标 3 继续，避免重复用同一个位置)。
21. 23每到一个节点先把当前 path 收进结果：[2,2]。
22. 24这条分支走完，撤销 2（path → [2]），回到上一层换下一个候选。
23. 25这条分支走完，撤销 2（path → []），回到上一层换下一个候选。
24. 26下标 2 的 2 和同层前一个下标 1 的 2 相同，这一层已经从 2 开过分支了，再选会产生重复子集 → 画 ✗ 剪掉。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def subsetsWithDup(nums):
    nums.sort()                 # 排序: 相同元素相邻
    res, path = [], []
    def dfs(start):
        res.append(path[:])     # 每个节点都是一个子集
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue        # 同层去重
            path.append(nums[i])
            dfs(i + 1)
            path.pop()          # 回溯撤销
    dfs(0)
    return res

vector<vector<int>> subsetsWithDup(vector<int>& nums){
    sort(nums.begin(), nums.end());
    vector<vector<int>> res; vector<int> path;
    function<void(int)> dfs = [&](int start){
        res.push_back(path);
        for(int i = start; i < nums.size(); ++i){
            if(i > start && nums[i] == nums[i-1]) continue;
            path.push_back(nums[i]);
            dfs(i + 1);
            path.pop_back();
        }
    };
    dfs(0);
    return res;
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);          // 排序: 相同元素相邻
        dfs(nums, 0);
        return res;
    }
    private void dfs(int[] nums, int start) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // 同层去重
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1); // 回溯撤销
        }
    }
}

复杂度

面试官可能追问