90. Subsets II

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],
  []
]

---

求一个“集合”的所有子集，和LeetCode Subsets的区别是本题中，原始“集合”可能包含重复元素，和LeetCode Permutations II很类似。
只需在LeetCode Subsets的基础上增加一个判断，如果在递归的时候发现某个元素和上一个元素相同，则不添加，即不再以该元素独立新开一个递归下去。
举个例子，样例中的{1,2,2}，第一次递归的时候，我们会尝试分别以1,2和2递归，但是发现第二个2和前一个元素2相同，所以我们不再以第二个2开一个新的递归下去。但是我们在以第一个2开递归的时候，发现后面有一个2时，并不阻止这个2加到原有的集合中去，也就是子集{2,2}还是会产生的。
完整代码如下：

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& cand, vector<int>& nums, int step)
    {
        ans.push_back(cand);
        for (int i = step; i < nums.size(); i++) {
            if (i != step && nums[i] == nums[i – 1]) { // caution:i != step
                continue;
            }
            cand.push_back(nums[i]);
            work(ans, cand, nums, i + 1);
            cand.pop_back();
        }
    }
    vector<vector<int> > subsetsWithDup(vector<int>& nums)
    {
        vector<vector<int> > ans;
        vector<int> cand;
        sort(nums.begin(), nums.end()); // 先对原数组排序
        work(ans, cand, nums, 0);
        return ans;
    }
};

注意判断的条件是i!=step，而不是i!=0，因为如果是i!=0，则{2,2}这种情况也会被禁止掉。
本代码提交AC，用时6MS。