Recursive

//参考 http://www.cnblogs.com/felixfang/p/3775712.html

class Solution {

public:

vector<vector<int>> ret;

vector<int> path;

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

sort(nums.begin(), nums.end());

helper(nums,0);

return ret;

}

void helper(vector<int>& nums, int step){

if(step==nums.size()){

ret.push_back(path);

return;

}

//consider both case: add S[start] into v; not add S[start] to v.

if(path.size() == 0 || nums[step]!=path[path.size()-1])

helper(nums,step+1);

//If S[start] == v[v.size()-1], we only need to consider the case add S[start] into v.

path.push_back(nums[step]);

helper(nums,step+1);

path.pop_back();

}

};