LeetCode --- 78. Subsets

タイトルリンク: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つの整数集合を与え,そのすべてのサブセットを返すことである.サブセットの要素は、重複サブセットを含まない非減算順に並べられることが要求されます.
1.遡及
Combinationsの拡張でしょう.Combinationsはk個の要素のサブセットを求めているが,この問題はすべてのサブセットを求めるので,Combinationsの考え方を利用して,各数字を順に開始として固定し,その後のn数字を再帰的に処理すればよい.再帰的にはnが層毎に減少するので,再帰終了条件はnが0に等しい場合に記録する必要がある.また、nが0からS.size()まで対応する場合をそれぞれ求める必要がある.
ここで、bはサブセットの開始位置であり、nはサブセットの要素数である.
時間複雑度:O(n*2^n)(結果数)
空間複雑度:O(n*2^n)(結果数)

 1 class Solution 
 2 {
 3     vector<vector<int> > vvi;
 4 public:
 5     vector<vector<int> > subsets(vector<int> &S) 
 6     {
 7         sort(S.begin(), S.end());
 8         vector<int> vi;
 9         vvi.push_back(vi);
10         for(int i = 1; i <= S.size(); ++ i)
11             subsets(S, vi, 0, i);
12         return vvi;
13     }
14 private:
15     // b        ，n        
16     void subsets(vector<int> &S, vector<int> &vi, int b, int n)
17     {
18         if(n == 0)
19             vvi.push_back(vi);
20         else
21             for(int i = b; i < S.size() + 1 - n; ++ i)
22             {
23                 vi.push_back(S[i]);
24                 subsets(S, vi, i + 1, n - 1);
25                 vi.pop_back();
26             }
27     }
28 };

2.ビット操作
n個の要素の集合で,2^nのサブセットがある.さらに、実は集合S中の各要素があるかないか、すなわちS中の各要素の状態が0または1である.したがって,S中の各要素の状態を0から2^v−1の低いnビットに対応させるとよい.
S={1,2,3}とすると、

i -> (3 2 1)
0 -> (0 0 0) -> { }
1 -> (0 0 1) -> {1}
2 -> (0 1 0) -> {2}
3 -> (0 1 1) -> {1 , 2}
4 -> (1 0 0) -> {3}
5 -> (1 0 1) -> {1 , 3}
6 -> (1 1 0) -> {2 , 3}
7 -> (1 1 1) -> {1 , 2 , 3}

時間複雑度:O(n*2^n)(結果数)
空間複雑度:O(n*2^n)(結果数)

 1 class Solution 
 2 {
 3 public:
 4     vector<vector<int> > subsets(vector<int> &S) 
 5     {
 6         sort(S.begin(), S.end());
 7         int l = 1 << S.size();
 8         vector<vector<int> > vvi(l, vector<int>());
 9         for(int i = 0; i < l; ++ i)
10             for(int j = 0; j < S.size(); ++ j)
11                 if(i & 1 << j) //   i j    1
12                     vvi[i].push_back(S[j]);
13         return vvi;
14     }
15 };

転載は出典:LeetCode---78.Subsets