No.78 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],
  []
]

回溯、位操作

方法一：
　　　　位向量法：深搜，时间复杂度O(n^2)，空间复杂度O(n)
　　　　设置一个位向量组selected，每个元素只有两种状态：选或者不选

 1 void subsets(const vector<int> &S, vector<bool> &selected, int step, vector<vector<int>> &result);
 2 vector<vector<int>> subsets(vector<int> &S)
 3 {
 4     sort(S.begin(),S.end());
 5 
 6     vector<vector<int>> result;
 7     vector<bool> selected(S.size(),false);
 8     subsets(S, selected, 0, result);
 9     return result;
10 }
11 
12 void subsets(const vector<int> &S, vector<bool> &selected, int step, vector<vector<int>> &result)
13 {
14     if(step == S.size())
15     {
16         vector<int> temp;
17         for(int i=0; i<S.size(); i++)
18         {
19             if(selected[i]==true)//=true与==true
20                 temp.push_back(S[i]);
21         }
22         result.push_back(temp);
23         return;
24     }
25 
26     //不选S[step]
27     selected[step] = false;
28     subsets(S, selected, step+1, result);
29     //选S[step]
30     selected[step] = true;
31     subsets(S, selected, step+1, result);
32 }

方法二：

　　　　二进制法:时间复杂度O(n^2)，空间复杂度O(1)

　　　　前提：数组中的元素数不超过int位数。用一个int整数表示位向量，第i位为1；表示选择S[i]为0，表示不选择。

　　　　这种方法最巧妙，其实可看做位向量法，只不过更加优化

 1 vector<vector<int>> subsets(vector<int> &s)
 2 {
 3     sort(s.begin(),s.end());//要求有序
 4     vector<vector<int>> result;
 5     const size_t size = s.size();//数组组成
 6     vector<int> temp;
 7 
 8     for(size_t i = 0; i<(1<<size); i++)
 9     {
10         for(size_t j = 0; j<size; j++)
11             if(i & (1<<j))
12                 temp.push_back(s[j]);
13         result.push_back(temp);
14         temp.clear();
15 
16     }
17     return result;
18 }

完整代码：

 1 #include "stdafx.h"
 2 #include <vector>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 /*
 8     //二进制法:时间复杂度O(n^2)，空间复杂度O(1)
 9 vector<vector<int>> subsets(vector<int> &s)
10 {
11     sort(s.begin(),s.end());//要求有序
12     vector<vector<int>> result;
13     const size_t size = s.size();//数组组成
14     vector<int> temp;
15 
16     for(size_t i = 0; i<(1<<size); i++)
17     {
18         for(size_t j = 0; j<size; j++)
19             if(i & (1<<j))
20                 temp.push_back(s[j]);
21         result.push_back(temp);
22         temp.clear();
23 
24     }
25     return result;
26 }
27 */
28 
29 //位向量法：深搜，时间复杂度O(n^2)，空间复杂度O(n)
30 //设置一个位向量组，每个元素只有两种状态：选或者不选
31 void subsets(const vector<int> &S, vector<bool> &selected, int step, vector<vector<int>> &result);
32 vector<vector<int>> subsets(vector<int> &S)
33 {
34     sort(S.begin(),S.end());
35 
36     vector<vector<int>> result;
37     vector<bool> selected(S.size(),false);
38     subsets(S, selected, 0, result);
39     return result;
40 }
41 
42 void subsets(const vector<int> &S, vector<bool> &selected, int step, vector<vector<int>> &result)
43 {
44     if(step == S.size())
45     {
46         vector<int> temp;
47         for(int i=0; i<S.size(); i++)
48         {
49             if(selected[i]==true)//=true与==true
50                 temp.push_back(S[i]);
51         }
52         result.push_back(temp);
53         return;
54     }
55 
56     //不选S[step]
57     selected[step] = false;
58     subsets(S, selected, step+1, result);
59     //选S[step]
60     selected[step] = true;
61     subsets(S, selected, step+1, result);
62 }
63 
64 int main()
65 {
66     const int data[6] = {0};
67     vector<int> s(data,data+1);
68     vector<vector<int>> result = subsets(s);
69     int count = 1;
70 
71     for(auto sub : result)
72     {
73         cout << count++ <<" : ";
74         for(auto ch : sub)
75             cout << ch << " ";
76         cout<<endl;
77     }
78     
79     return 0;
80 }

View Code