描述

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

思路

这道题对照着第78题.子集来看，只不过将无重复数字换成了有重复数字。按照78题的做法，只要做些许更改即可。

首先需要对原nums数组进行排序，将重复元素挨到一起后有利于迭代过程中进行剪枝。还是按照上题的思路，每次取res结果中的每个元素，将其加入nums[i]变成新子集后加入到res中。但是当碰到重复元素时，就不能这样做了，因为重复元素在此元素第一次出现的时候已经形成过部分组合了，再执行此步骤会造成重复，因此找一下规律，发现只需要在此元素第一次出现时形成的新序列基础上加入这个重复元素即可，不需要遍历整个res，这就需要一个tmpRes来存储元素第一次出现时生成的新序列。不管是否碰到重复的数字，都将本次生成的序列记录到tmpRes中。

取一个例子[1,2,2,3]，具体执行步骤如图：

解答

class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<vector<int> > res = {{}};//新建vector时插入一个空集，作为最终结果vector<vector<int> > tmpRes;//tmpRes存储重复的数字加入后构成的新集合sort(nums.begin(), nums.end());for(int i = 0;i < nums.size();++ i){//每次选择所给数组中的一个数字if(i == 0 || i >= 1 && nums[i] != nums[i-1]){tmpRes.clear();int size = res.size();for(int j = 0;j < size; ++ j){vector<int> tmp = res[j];//遍历获取到res中的每一个vector，将nums[i]放入tmp.push_back(nums[i]);tmpRes.push_back(tmp);//更新tmpRes}}else if(i >= 1 && nums[i] == nums[i-1]){int size = tmpRes.size();for(int j = 0;j < size; ++ j){vector<int> tmp = tmpRes[j];//遍历获取到tmpRes中的每一个vector，将nums[i]放入tmp.push_back(nums[i]);tmpRes[j] = tmp;//更新tmpRes}}res.insert(res.end(), tmpRes.begin(), tmpRes.end());//将tmpRes元素插入res中     }return res;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！