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.
就是找出数字的全部子集。
我的思路：
设输入是 1 2 3 4
先把输入从小到大排序
长度 0 : []
长度 1 : 把输入数据从第一个数开始 1， 找上一个数字结果中开始数字比1大的解 没有 直接压入 [1]
2，找上一个数字结果中开始数字比2大的解 没有 直接压入 [2]
...
得到长度为1的解是 [1] [2] [3] [4]
长度 2 : 把输入数据从第一个数开始 1， 找上一个数字结果中开始数字比1大的解 有[2] [3] [4]， 压入[1 2][1 3][1 4]
2， 找上一个数字结果中开始数字比2大的解 有 [3] [4]， 压入[2 3][2 4]
...
得到长度为2的解是 [1 2][1 3][1 4][2 3][2 4][3 4]
长度 3 : 把输入数据从第一个数开始 1， 找上一个数字结果中开始数字比1大的解 有[2 3][2 4][3 4]， 压入[1 2 3][1 2 4][1 3 4]
2， 找上一个数字结果中开始数字比2大的解 有 [3 4]， 压入[2 3 4]
得到长度为3的解是 [1 2 3][1 2 4][1 3 4][2 3 4]
长度 4 : 把输入数据从第一个数开始 1， 找上一个数字结果中开始数字比1大的解 有[2 3 4]， 压入[1 2 3 4]
2， 找上一个数字结果中开始数字比2大的解 没有
得到长度为4的解是 [1 2 3 4]
代码用了posfirst,poslast来表示上一个长度答案的范围。
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());
vector<vector<int>> ans;
vector<int> partans;
ans.push_back(partans); //空的
int posfirst = ; //上一个长度子集在ans中的起始下标
int poslast = ; //上一个长度子集在ans中的结束下标
for(int len = ; len <= S.size(); len++) //对长度循环
{
poslast = ans.size() - ;
for(int i = ; i < S.size(); i++) //对起始数字循环
{
while(!ans[posfirst].empty() && S[i] >= ans[posfirst][] && posfirst <= poslast) //跳过上一个长度答案中起始数字小于等于当前起始数字的解
{
posfirst++;
}
for(int pos = posfirst;pos <= poslast; pos++) //获取当前的答案
{
partans.push_back(S[i]); //压入当前数字
for(int j = ; j < ans[pos].size(); j++) //压入上一个长度答案中的数字
{
partans.push_back(ans[pos][j]);
}
ans.push_back(partans);
partans.clear();
}
}
posfirst = poslast + ;
}
return ans;
}
};
大神的解法：https://oj.leetcode.com/discuss/9213/my-solution-using-bit-manipulation
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort (S.begin(), S.end());
int elem_num = S.size();
int subset_num = pow (, elem_num);
vector<vector<int> > subset_set (subset_num, vector<int>());
for (int i = ; i < elem_num; i++)
for (int j = ; j < subset_num; j++)
if ((j >> i) & )
subset_set[j].push_back (S[i]);
return subset_set;
}
};
解释如下：
This is an amazing solution.Learnt a lot.Let me try to explain this to those who didn't get the logic.
Number of subsets for { , , } = ^ .
why ?
case possible outcomes for the set of subsets
-> Take or dont take =
-> Take or dont take =
-> Take or dont take =
therefore , total = ** = ^ = { { } , {} , {} , {} , {,} , {,} , {,} , {,,} }
Lets assign bits to each outcome -> First bit to , Second bit to and third bit to
Take =
Dont take =
) -> Dont take , Dont take , Dont take = { }
) -> Dont take , Dont take , take = { }
) -> Dont take , take , Dont take = { }
) -> Dont take , take , take = { , }
) -> take , Dont take , Dont take = { }
) -> take , Dont take , take = { , }
) -> take , take , Dont take = { , }
) -> take , take , take = { , , }
In the above logic ,Insert S[i] only if (j>>i)& ==true { j E { ,,,,,,, } i = ith element in the input array }
element is inserted only into those places where 1st bit of j is
if( j >> & ) ==> for above above eg. this is true for sl.no.( j )= , , ,
element is inserted only into those places where 2nd bit of j is
if( j >> & ) == for above above eg. this is true for sl.no.( j ) = , , ,
element is inserted only into those places where 3rd bit of j is
if( j >> & ) == for above above eg. this is true for sl.no.( j ) = , , ,
Time complexity : O(n*^n) , for every input element loop traverses the whole solution set length i.e. ^n