力扣每日一题90：子集

题目描述：

给你一个整数数组 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

通过次数

330.7K

提交次数

520.9K

通过率

63.5%

思路和题解

如果说数组里没有重复元素的话，我们可以用回溯法，每次都遍历没有用过的数，对于遍历的数，选择放入这个数字或不放这个数字。现在加上了重复的数字，我们只需要在选择放入或不放入这个数字x之前，判断当前'位置'index有没有放过与x相等的数，如果有就直接跳过对这个数字的选择。

对于   判断当前'位置'index有没有放过与x相等的数   ，我们可以先将数组排序，排序后，相等的数字都相邻，这样就用if(i!=depth&&nums[i]==nums[i-1]) continue;判断是否有重复。

代码：

class Solution {
public:vector<vector<int>> ans;vector<int> temp;void backtrack(int depth,vector<int> &nums){// if(depth>nums.size()) return ;ans.emplace_back(temp);for(int i=depth;i<nums.size();i++){//有重复就跳过这个数字if(i!=depth&&nums[i]==nums[i-1]) continue;//选择这个数字temp.emplace_back(nums[i]);backtrack(i+1,nums);//不选择这个数字temp.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());backtrack(0,nums);return ans;}
};