Lintcode: 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.

Tags Expand 

Recursion

Reference:
https://siddontang.gitbooks.io/leetcode-solution/content/backtracking/subsets.html

Just add lines from 24 to 26

Repetition happens not in DFS, but same level i point to same number

Time: O(n!)
Space: O(n)

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<int> nums(S); vector<vector<int> > res; vector<int> tempres; sort(nums.begin(), nums.end()); res.push_back(tempres); DFS(0, nums, tempres, res); return res; } private: void DFS(int start, vector<int> &nums, vector<int> &tempres,vector<vector<int> > &res){ for(int i = start; i < nums.size(); i++){ tempres.push_back(nums[i]); DFS(i + 1, nums, tempres, res); res.push_back(tempres); tempres.pop_back(); while((i + 1) < nums.size() && nums[i] == nums[i+1]){ i++; } } } };

Lintcode second:

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

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 vector<int> nums(S); sort(nums.begin(), nums.end()); vector<vector<int> > allsol; vector<int> sol; allsol.push_back(sol); DFS(0, nums, sol, allsol); return allsol; } void DFS(int start, vector<int> &S, vector<int> &sol, vector<vector<int> > &allsol){ for(int i = start; i < S.size(); i++){ //here to deal with deep level DFS() sol.push_back(S[i]); allsol.push_back(sol); DFS(i + 1, S, sol, allsol); sol.pop_back(); //here to deal with same level DFS() while(i + 1 < S.size() && S[i] == S[i + 1]) i++; } } };