LinceCode (18) Subsets II

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

Have you met this question in a real interview? 

Yes

Example

If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Note

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.

和subsets一样，只是多了一个剪枝的过程， 如果画一下的话：

()< 1, 2, 2

(1) < 2, 2    (2)< 1, 2  (2) < 1, 2 去掉第三个

拿 (1) <2, 2再举例， （1 ，2） 2   (1, 2) 2 去掉第二个

由此可以看出，再同一个元素位置，我们只需要把第一个2放进去，后面的就可以忽略掉。 这种策略其实在很多题目中都用到了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

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 vector< vector<int> > result; vector<int> solution; vector<int> input(S.begin(), S.end()); sort(input.begin(), input.end()); dfs(result, solution, input, 0); return result; } void dfs(vector< vector<int> >& result, vector<int>& solution,const vector<int>& S, int index){ result.push_back(solution); for (int i= index; i<S.size(); i++){ // at the same level, we should only take one if (i!=index && S[i]==S[i-1]){ continue; } solution.push_back(S[i]); dfs(result,solution,S, i+1); solution.pop_back(); } } };