## Monday, November 17, 2014

### [LeetCode] Subsets I, II

Subsets I

Given a set of distinct integers, 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,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

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],
[]
]

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: vector > subsets(vector &S) { vector> allSets; vector sol; allSets.push_back(sol); sort(S.begin(),S.end()); findSubsets(S, 0, sol, allSets); return allSets; } void findSubsets(vector &S, int start, vector &sol, vector> &allSets) { for(int i=start; i

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: vector > subsets(vector &S) { vector> allSets; vector sol; allSets.push_back(sol); sort(S.begin(), S.end()); for(int i=0; i

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: vector > subsets(vector &S) { vector> allSets; sort(S.begin(), S.end()); unsigned long long maxNum = pow(2, S.size()) - 1; for(unsigned long long i=0; i<=maxNum; i++) allSets.push_back(num2subset(S, i)); return allSets; } vector num2subset(vector &S, unsigned long long num) { vector sol; int i=0; while(num) { if(num & 1) sol.push_back(S[i]); num >>= 1; i++; } return sol; } };

1. 一定要先排序
2. 调用下一层递归时(ln 17)，起始index 一定是i+1而不能错写成start+1

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: vector > subsetsWithDup(vector &S) { vector> allSets; vector sol; allSets.push_back(sol); sort(S.begin(), S.end()); findSubsetsWithDup(S, 0, sol, allSets); return allSets; } void findSubsetsWithDup(vector &S, int start, vector &sol, vector> &allSets) { for(int i=start; istart && S[i]==S[i-1]) continue; sol.push_back(S[i]); allSets.push_back(sol); findSubsetsWithDup(S, i+1, sol, allSets); sol.pop_back(); } } };