【小白爬Leetcode90】4.2 子集II SubsetsII

题目discription中文描述分析 思路一 利用set来记录是否重复(回溯法)改进 思路二 优先选择重复元素中的后者（回溯法） Leetcode 90 $medium$

这道题的先导：Leetcode 78 子集 Subsets

点击进入原题链接：Leetcode 90 子集II SubsetsII

题目

discription

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

中文描述

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

说明：解集不能包含重复的子集。

分析

这道题和Leetcode 78 子集 Subsets最大的区别在于，78题给出的nums没有重复元素，因此也不要求最后给出的子集集合不重复，而这道题给出的nums存在重复元素，因此需要对最终的结果进行去重。

以nums={2,1,2,2}为例，重复无非两种情况：

两个子集顺序相同的重复，如{2,1,2}和{2,1,2}，这种可以通过set轻松去重；两个子集顺序不同的重复，如{2,1,2}和{1,2,2}，这种无法通过set去重；

为了解决第二种重复，我们需要将nums进行排序： nums={1,2,2,2} 这样重复只会出现第一种情况，而不会出现而第二种了。

总的来说，思路一共有如下组合：回溯or位运算 x set去重or手动跳过法，因此本质上有2*2=4种解法，至于手动跳过法里还有从前到后和从后到前两种思路，我觉得前者不是很好理解，就不放出来了。

思路一 利用set来记录是否重复(回溯法)

class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end(),less()); //上来对nums进行排序 vector<int> items; // items是不断更新的一个子序列 vector<vector<int>> ret; // 最终要返回的二维数组 ret.push_back(items); // 先把[]加进ret里 set<vector<int>> ret_set; //构建一个装有各个子序列的set<vector<int>> subset_builder(0,nums,items,ret,ret_set); //自己定义的一个递归函数，用来求ret return ret; } private: void subset_builder(int idx,vector<int>& nums,vector<int>& items,vector<vector<int>>& ret,set<vector<int>>& ret_set){ // idx是nums的索引，items是不断更新的一个子序列，ret是最终要返回的结果，ret_set是储存子序列的去重set if(idx>=nums.size()){ return; } items.push_back(nums[idx]); if(ret_set.find(items)==ret_set.end()){ //如果在去重set里没找到目前的items ret.push_back(items); ret_set.insert(items); } subset_builder(idx+1,nums,items,ret,ret_set); items.pop_back(); subset_builder(idx+1,nums,items,ret,ret_set); } };

由于使用了一个额外的关联式容器，因此时间和空间上都很耗费机时。

改进

上述方法对set的使用并不够高效：因为每一步都需要判断是否要往set里添加vector<int>，这里做了一些改进：先把所有可能的子集加入ret，最后再一次性去重。

class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end(),less<int>()); //上来对nums进行排序 vector<int> items; // items是不断更新的一个子序列 vector<vector<int>> ret; // 最终要返回的二维数组 subset_builder(0,nums,items,ret); //自己定义的一个递归函数，用来求ret set<vector<int>> s(ret.begin(),ret.end()); ret.assign(s.begin(),s.end()); return ret; } private: void subset_builder(int idx,vector<int>& nums,vector<int>& items,vector<vector<int>>& ret){ // idx是nums的索引，items是不断更新的一个子序列，ret是最终要返回的结果，ret_set是储存子序列的去重set if(idx == nums.size()){ ret.push_back(items); return; } items.push_back(nums[idx]); subset_builder(idx+1,nums,items,ret); items.pop_back(); subset_builder(idx+1,nums,items,ret); } };

思路二 优先选择重复元素中的后者（回溯法）

思路来自于Leetcode的 sleeping monster，思路是：

先对nums数组进行排序；当选择不包含当前元素的分支的时候，需要考虑去重： 如果当前元素nums[i]是重复元素的第一个，那么跳过该元素,直到该重复元素的最后一个。 以[1,1,2,2]为例，打叉表示被修剪的分支，可以看到，被修剪的都是右分支的重复节点。

例如：

第0个元素的左分支为items=[1]，右分支不包含第0个元素int 1，为items=[]；第1个元素int 1与第0个雷同，因此：如果选择第1个元素，则items==[1]与第0个元素的左分支雷同；如果不选择第1个元素，则items=[]与自己雷同。综上第0个元素的右分支应该跳过第1个元素，直接考虑第2个元素。

如果将nums里相同的元素视作兄弟的话，那么总结起来就是：如果抛弃了大哥，那么二哥，三哥…都不能再考虑了；抛弃了二哥，那么三哥，四哥都不能再考虑了。

最后蓝色下划线表示输出。