【3.31】LeetCode每日一题· 子集II

2021年03月31日 10时45分

标签： LeetCode dfs 数组

## 题目描述
给你一个整数数组`nums`，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集**不能**包含重复的子集。返回的解集中，子集可以按**任意顺序**排列。

#### 示例1
```
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
```

#### 示例2
```
输入：nums = [0]
输出：[[],[0]]
```

#### 提示
```
1 <= nums.length <= 10
-10 <= nums[i] <= 10
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/subsets-ii/ "题目链接")

## 解题思路
如果数组中**不包含重复元素**，就是一个简单的**dfs**。

但是目前数组中可能包含重复元素，那么如何去重？

考虑`[1, 2, 2]`，选择**第1个、第2个**元素的子集和选择**第1个、第3个**元素的子集是相同的，但和选择**第2个、第3个**元素的子集是不同的，也就是说，如果我们将数组排序，则：

**当当前元素和其前一个元素值相等，且未选择前一个元素时，包含当前元素的子集和包含前一个元素的子集相同**

此时就可以直接不选择当前的元素，而跳到后一个元素继续进行递归。

在代码中，可以使用一个变量`flag`记录当前元素的前一个元素是否被选中，注意判断第一个元素防止数组越界。

Tips: 如果将递归使用位掩码改成迭代的话，内存消耗会少一点。

### 代码
```cpp
class Solution {
private:
    vector<vector<int>> res;
    vector<int> tmp; 
    void dfs(vector<int>& nums, int dps, int flag){
        if(dps == nums.size()){
            res.emplace_back(tmp);
            return;
        }
        dfs(nums, dps+1, 0);
        if(flag){
            tmp.emplace_back(nums[dps]);
            dfs(nums, dps+1, 1);
            tmp.pop_back();
        }else{
            if(dps == 0 || nums[dps-1] != nums[dps]){
                tmp.emplace_back(nums[dps]);
                dfs(nums, dps+1, 1);
                tmp.pop_back();
            }
        }
        
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0);
        return res;
    }
};
```

## 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：11.4 MB，在所有 C++提交中击败了6.88%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.31】LeetCode每日一题· 子集II

所有评论

暂无评论

新增评论