题目链接：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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution 
{
    vector<vector<int> > vvi;
public:
    vector<vector<int> > subsets(vector<int> &S) 
    {
        sort(S.begin(), S.end());
        vector<int> vi;
        vvi.push_back(vi);
        for(int i = 1; i <= S.size(); ++ i)
            subsets(S, vi, 0, i);
        return vvi;
    }
private:
    // b为子集的起始位置，n为子集的元素数量
    void subsets(vector<int> &S, vector<int> &vi, int b, int n)
    {
        if(n == 0)
            vvi.push_back(vi);
        else
            for(int i = b; i < S.size() + 1 - n; ++ i)
            {
                vi.push_back(S[i]);
                subsets(S, vi, i + 1, n - 1);
                vi.pop_back();
            }
    }
};

  1. 位操作

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution 
{
public:
    vector<vector<int> > subsets(vector<int> &S) 
    {
        sort(S.begin(), S.end());
        int l = 1 << S.size();
        vector<vector<int> > vvi(l, vector<int>());
        for(int i = 0; i < l; ++ i)
            for(int j = 0; j < S.size(); ++ j)
                if(i & 1 << j) // 判断i的j位是否为1
                    vvi[i].push_back(S[j]);
        return vvi;
    }
};