LintCode(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.

画一画就知道了，每次遍历的时候只取出第一个有重复的数字就是了。。。所以加了个剪枝。。。

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

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, vector<int>& input, int ind){ result.push_back(solution); if(solution.size()==input.size()) return; for (int i= ind; i<input.size(); i++){ if (i!=ind && input[i]==input[i-1]) continue; solution.push_back(input[i]); dfs(result, solution, input, i+1); solution.pop_back(); } } };