原题传送门->>>

题目描述：

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.

示例：

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

简单的回溯题，但是自己解决时遇到很多问题，记录一下。

AC代码

class Solution {
public:
    vector<vector<int>>ans;
    vector<int> tmp;
    int* mark;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        mark = new int[nums.size()];
        memset(mark, 0, 4 * nums.size());
        for (int i = 0; i < nums.size(); ++i)
            select(nums, i);
        delete[]mark;
        ans.push_back(vector<int>());
        return ans;
    }
    void select(vector<int>& nums, int pos)//将要取pos元素
    {
        if (pos == nums.size())
            return;
        if (pos && (nums[pos] == nums[pos - 1]) && (!mark[pos - 1]))
            return;
        else
        {
            tmp.push_back(nums[pos]);
            ans.push_back(tmp);
            mark[pos] = 1;
            for (int i = pos + 1; i < nums.size(); ++i)
            select(nums, i);
            tmp.pop_back();
            mark[pos] = 0;

        }
    }

};

去重的规则比较清楚：先进行排序。
取规则：当多个相同数字连续出现，这几个相同数字必须从左到右取，不能有间隔。

比如：array = [1，2，3，3，3] 假如不取array[2]，那么array[3],array[4]也不可以取。

问题在于搜索上。

WA代码版本1

//           for (int i = pos + 1; i < nums.size(); ++i)
//          select(nums, i);
select(nums, pos + 1);

这个版本是深搜时仅仅探测下一格。它不允许连续取元素。比如array = [1，2，3，3，3]，[1,3]不会出现在答案中

WA代码版本2

//if (pos && (nums[pos] == nums[pos - 1]) && (!mark[pos - 1]))
//    return;
if (pos && (nums[pos] == nums[pos - 1]) && (!mark[pos - 1]))
 {
    for (int i = pos + 1; i < nums.size(); ++i)
       select(nums, i);
return;
 }

这种情况，当发现重复元素不符合取规则时,会对后面的所有元素进行探测。问题在于，当return之后，该点之后的所有元素会再被探测一遍，结果答案会有大量重复。