090 - Subsets II

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Hide Tags
Array Backtracking
比较偷懒的做法是在第一题的结果上，再sort一下，用unique去重。
仔细观察一下push的过程，会发现，
当处理完一个起点的递归之时，再其下一层的调用返回之前，
想要避免重复的结果，就是直接跨到下一个不同的元素上去，

例如 [1, 2, 2, 3]
当start是1的时候，假设要处理的count是2，即，只取两个数组来组合，
递归调用进去start’ 是第一个2，这时候满足了两个数字，
所以再次递归进去就push当前这个组合到结果区了。
然后返回，如果这时候继续循环，start’’ 是第二个2，就会出现重复的 [1, 2] 了
所以需要跳过第二个 2， 直到遇到 3。
这样做并不影响 [2, 2]，因为从2进来，并没有先跳过，而是处理完了才跳过，
所以就算有n个2，都可以处理。
配合count，对于重复的元素，就可以产生完全的组合了。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> rst;
        vector<int> buf;
        rst.push_back(buf);

        int sz = nums.size();
        if(sz)
        {
            sort(nums.begin(), nums.end());
            for(int nn=1; nn<=sz; ++nn)
                build(nums, sz, rst, buf, nn, 0, 0);
        }

        return rst;
    }
   
    void build(vector<int>& nums, int sz, vector<vector<int>>& rst,
                    vector<int>& buf, int count, int taken, int start)
    {
        if(taken==count)
            rst.push_back(buf);
        else
        {
            int end=sz-count+taken;
            for(int ii=start; ii<=end; ++ii)
            {
                buf.push_back(nums[ii]);
                build(nums, sz, rst, buf, count, taken+1, ii+1);
                buf.pop_back();
               
                while((ii<=end)&&(nums[ii]==nums[ii+1]))
                    ii++;
            }
        }
        return;
    }
};

12 ms.



讨论区有个帖子，提到了三种解法，可以参考。
下面是他提到的递归，写得更简洁：

//recursive 8ms
vector<vector<int>> res;
int n;
void generate(vector<int>& num, vector<int>& tmp, int k) {
    res.push_back(tmp);  //每次进来，先把已经取到的元素作为一个结果push进去
    for (int i = k; i < n; i++) {
        tmp.push_back(num[i]);      //在已经走到的元素后面继续追加
        generate(num, tmp, i + 1);  //递归进去，
        tmp.pop_back();
        while (i < n - 1 && num[i] == num[i + 1]) {  //跳过重复的部分
            i++;
        }
    }
}

vector<vector<int>> subsetsWithDup3(vector<int>& nums) {
    n = nums.size();
    vector<int> tmp;
    sort(nums.begin(), nums.end());
    generate(nums, tmp, 0);
    return res;
}