题目链接：90. 子集 II

题解：

又是不能重复的递归问题，和LeetCode刷题-47.全排列II此题的关键位置有点像！

题目简述：

给定一个包含重复元素的无序序列，返回该序列可以构成的不能重复的所有组合！

题解：

递归：

关键部分：如何去重？

  • 首先将数组排序，使得相同元素挨到一起
  • 对于1 2 2来说，处理1 x x时，第二位只使用第一个2即可，不要让他使用第二个2即可！
  • i <= start ：保证该位置的第一次选择直接使用第一个重复元素
  • i <= start && nums[i] == nums[i - 1]：保证该位置的下一种选择方案要保证不是重复元素

时间复杂度：最多有 2^n 个子集，每个子集存储需要O(n)计算量，总时间复杂度为：O(n * 2^n)

AC代码一：

for循环去处理长度为0 ~ n的情况！

递归出口：当前位数 == 需要位数，即u == n

AC代码二更加简洁！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path, nums;
    vector<vector<int>> subsetsWithDup(vector<int>& _nums) {
        nums = _nums;
        sort(nums.begin(), nums.end());
        for(int i = 0; i <= nums.size(); i++) dfs(i, 0, 0);
        return res;
    }
    void dfs(int n, int u, int start){
        if(u == n){
            res.push_back(path);
            return;
        }
        for(int i = start; i < nums.size(); i++){
            if(i > start && nums[i] == nums[i - 1]) continue;
            path.push_back(nums[i]);
            dfs(n, u + 1, i + 1);
            path.pop_back();
        }
    }
};

AC代码二：

不用那么麻烦，使用for循环，由于递归本就是一颗二叉树，所以到达每个节点都是一种情况，所以可以像下面这样写！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path, nums;
    vector<vector<int>> subsetsWithDup(vector<int>& _nums) {
        nums = _nums;
        sort(nums.begin(), nums.end());
        dfs(0);
        return res;
    }
    void 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();
        }
    }
};