Subsets
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],
[]
]
1. (a)
I would like to call it induction
•For n=1, the set of subsets is {{}, {S[0]}}
•For n>1, find the subsets of 1,...,n-1. Make two copies of it. For one of them, add n to each subset.
Then take the union of the two copies.
For example,
•The set of subsets of {S[0]} is {{}, {S[0]}}
•For {S[0], S[1]}, take {{}, {S[0]}}, add S[1], to each subset to get {{ S[1]}, { S[0], S[1]}} and take the union with {{}, { S[0]}} to get {{}, {S[0]}, {S[1]}, {S[0], S[1]}}
•Repeat till you reach S[n-1] (or finish all the elements)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> res;
if (S.empty()) return res;
int n = S.size();
sort(S.begin(),S.end());
vector<int> empty;
res.push_back(empty);
for (int i=0; i<n; i++)
{
vector<vector<int>> tmp=res;
for (int j=0; j<tmp.size();j++)
{
tmp[j].push_back(S[i]);
}
for (int j=0; j<tmp.size();j++)
{
res.push_back(tmp[j]);
}
}
return res;
}
};
1(b). Same idea, different implementation. 增量构造法 Ref:
http://m.blog.csdn.net/blog/mysee1989/39619401
Using vector::back() will simplify the code
http://www.cplusplus.com/reference/vector/vector/back/
vector<vector<int> > subsets(vector<int> &s) {
vector<vector<int>> res;
if (s.empty()) return res;
sort(s.begin(), s.end());
res.clear();
res.resize(1);
int n = s.size();
for (int i = 0; i<n; i++)
{
int size = res.size();
for (int j = 0; j<size; j++)
{
res.push_back(res[j]);
res.back().push_back(s[i]);
}
}
return res;
}
2. Backtracking with recursion. We need to set a bool vector as the solution vector a
class Solution {
public:
vector<vector<int> > subsets(vector<int> &s) {
vector<vector<int>> ret;
int n=s.size();
//if (n==0) return ret;
sort(s.begin(),s.end());
vector<bool> a(n,false);
helper(s,a,ret,n,0);
return ret;
}
void helper(vector<int> &s, vector<bool> &a, vector<vector<int>> &r, int n, int k)
{
if (k==n)
{
//process sol
vector<int> v;
for (int j = 0; j<n; j++)
{
if (a[j] == true)
v.push_back(s[j]);
}
r.push_back(v);
return;
}
else
{
a[k]=true;
helper(s,a,r,n,k+1);
a[k]=false;
helper(s,a,r,n,k+1);
}
}
};
3. This is to use an int's bits as a mask for solution vector. If i's position is 1, then choose S[i], otherwise, do not include S[i] in the solution vector.
For example, for n=3 or {1,2,3}, lets assign bits to each outcome -> First bit to 1 , Second bit to 2 and third bit to 3
Has = 1
No = 0
0) 0 0 0 -> No 3 , No 2 , No 1 = { }
1) 0 0 1 -> No 3 , No 2 , Has 1 = {1 }
2) 0 1 0 -> No 3 , Has 2 , No 1 = { 2 }
3) 0 1 1 -> No 3 , Has 2 , Has 1 = { 1 , 2 }
4) 1 0 0 -> Has 3 , No 2 , No 1 = { 3 }
5) 1 0 1 -> Has 3 , No 2 , Has 1 = { 1 , 3 }
6) 1 1 0 -> Has 3 , Has 2 , No 1 = { 2 , 3 }
7) 1 1 1 -> Has 3 , Has 2 , Has 1 = { 1 , 2 , 3 }
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> res;
if (S.empty()) return res;
sort(S.begin(),S.end());
int n=S.size();
int numVec = pow(2,n);
for (int i=0; i<numVec; i++)
{
vector<int> v;
for (int j=0; j<n; j++)
{
if (i&1<<j)
v.push_back(S[j]);
}
res.push_back(v);
v.clear();
}
return res;
}
};
