[leetcode]Subsets II

Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
这个曾经让我很捉鸡的题目。。。为什么这次用了个很烂的dfs，一次性通过，而且是80ms过大集合。。。。太讽刺了。。。

class Solution {
    set> result;
public:
    void dfs(vector&S, int i, vector tmp){
        if(i == S.size()){
            sort(tmp.begin(), tmp.end());
            result.insert(tmp);
            return;
        }
        dfs(S, i+1, tmp);
        
        tmp.push_back(S[i]);
        dfs(S, i+1, tmp);
        
        
    }
    

    vector > subsetsWithDup(vector &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        result.clear();
        vector tmp;
        dfs(S, 0, tmp);
        set>::iterator it;
        
        vector> ret;
        for(it = result.begin(); it!=result.end(); it++){
            ret.push_back(*it);
        }
        
        return ret;
       
    }
};