Subsets II

题目：

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice

Each element in a subset must be in non-descending order.

The ordering between two subsets is free.

The solution set must not contain duplicate subsets.

接口：

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(const vector<int> &S) {
        // write your code here

    }
};

分析：

因为是subsets,第一次是[1]，第二次从[1, 2]考虑，而不能重复使用[1, 1, 1, 1....]这样的情况，所以需要判断if isUsed[i] == true;

因为数组有重复元素，在[1, 2, 2]这种例子里面两个2有顺序，所以当nums[i - 1] == nums[i]的时候，需要判断isUsed[i - 1] == false的问题。

每次都push一个结果就好。

解法：

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */

    void dfs(vector<int> nums, 
                vector<int> instance, 
                vector<bool>& isUsed, 
                vector<vector<int> >& results,
                int start) {

        results.push_back(instance);

        for (int i = start; i < nums.size(); i++) {

            if (isUsed[i] == true) {
                continue;
            }

            if (i != 0 && nums[i] == nums[i - 1] && isUsed[i - 1] == false) {
                continue;
            }

            instance.push_back(nums[i]);
            isUsed[i] = true;
            dfs(nums, instance, isUsed, results, i);
            isUsed[i] = false;
            instance.pop_back();
        }
    } 

    vector<vector<int> > subsetsWithDup(const vector<int> &S) {
        // write your code here
        if (S.size() == 0) {
            return vector<vector<int> >();
        }

        vector<int> nums = S;
        sort(nums.begin(), nums.end());

        vector<vector<int> > results;
        vector<int> instance;
        vector<bool> isUsed(nums.size(), false);

        dfs(nums, instance, isUsed, results, 0);

        return results;
    }
};