90. Subsets II

problem description

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:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

algorithm thought

得到子集问题，和之前的第一题相比，多了重复数字，在计算子集的时候，需要处理重复情况。这里可以用和第一题类似的回溯法。也可以一次次将新数字push_back到之前得到的结果中，得到新的子集。

code

//类似上一题，直接用回溯法解决问题
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp{};
        res.push_back(tmp);
        sort(nums.begin(),nums.end());
        help(res,tmp,nums,0);
        return res;
    }
    void help(vector<vector<int>>&res,vector<int>&tmp,vector<int>&nums,int pos){
        if(pos==nums.size())
            return;
        for(int i=pos;i<nums.size();++i){
            if(i!=pos&&nums[i-1]==nums[i])
                continue;
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            help(res,tmp,nums,i+1);
            tmp.pop_back();
        }
    }
};

//一直对之前得到的结果处理，然后将得到的新数组push进res，一直重复，知道最后一个数字
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res={{}};
        sort(nums.begin(),nums.end());
        int start=1;
        res.push_back({nums[0]});
        for(int i=1;i<nums.size();++i){
            if(nums[i]!=nums[i-1])
                start=0;
            for(int j=res.size();start<j;start++){
                vector<int>tmp=res[start];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
            }
        }
        return res;
    }
};

algorithm analysis

得到所有的子集问题，回溯法时间复杂度O(2^n)。每个数字可以出现一个也可以不出现，每个数字都会进行两次计算，两个分支。最后得到2^n