计算机科学基础leetcode刷题回溯算法
Source
Edit
History

90. 子集 II

Problem: 90. 子集 II

Reference

代码随想录 (programmercarl.com)

思路

本题与40.组合总和II
的区别甚至只有,这个题目是求子集,需要每个path都加入集合。

还有要注意的点过滤条件,if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])讲的意思是,过滤掉同一层被使用过的。

不过这个去重有点抽象,代码随想录中这样解释:

1
2
// used[i - 1] == true，说明同一树**枝**candidates[i - 1]使用过
// used[i - 1] == false，说明同一树**层**candidates[i - 1]使用过

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;
    void backTracing(vector<int>& nums, int startIndex) {
        res.push_back(path);
        if (startIndex >= nums.size()) {
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
                continue;
            path.push_back(nums[i]);
            used[i] = true;
            backTracing(nums, i + 1);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        used = vector<bool>(nums.size());
        sort(nums.begin(), nums.end());
        backTracing(nums, 0);
        return res;
    }
};