阜蒙县建设镇官方网站,php网站建设设计报告,网站建好了seo怎么做,泰州专业制作网站题目描述#xff1a;
给你一个整数数组 nums #xff0c;其中可能包含重复元素#xff0c;请你返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。返回的解集中#xff0c;子集可以按 任意顺序 排列。 示例 1#xff1a;
输入#x…题目描述
给你一个整数数组 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!depthnums[i]nums[i-1]) continue;判断是否有重复。
代码
class Solution {
public:vectorvectorint ans;vectorint temp;void backtrack(int depth,vectorint nums){// if(depthnums.size()) return ;ans.emplace_back(temp);for(int idepth;inums.size();i){//有重复就跳过这个数字if(i!depthnums[i]nums[i-1]) continue;//选择这个数字temp.emplace_back(nums[i]);backtrack(i1,nums);//不选择这个数字temp.pop_back();}}vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(),nums.end());backtrack(0,nums);return ans;}
};
