78. 子集

Solution1：

对于每一项相对每个子集来说，都有放与不放两种选择。

创建一个放元素的递归函数，该函数的作用为将一项放和不放两种选择进行描述。

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
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        
        putitem(0, nums, item, result);
        return result;
    }
    //把一项放进result中。
    void putitem(int i, vector<int>& nums,vector<int> item, vector<vector<int> > &result){
        if(i == nums.size()){
            return;
        }
        //每个元素都有放和不放两种选择。
        //放
        item.push_back(nums[i]);
        result.push_back(item);
        putitem(i+1, nums, item, result);
        //不放
        item.pop_back();
        putitem(i+1, nums, item, result);
    }
};

Solution2：

遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int> > subsets(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        for(int i =0; i < nums.size(); i++){
            int s = result.size();
            for(int j = 0; j < s;j++){
                result.push_back(result[j]);
                result[j].push_back(nums[i]);
            }
        }
        return result;
    }
};

Solution3（位运算）：

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
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result;
        //子集一共有2的n次方种，使用位运算来解。
        //每一位代表一个元素。
        //如，100 代表[3]、011代表[2,1]。
        int all_set = 1 << nums.size();//2的n次方种；
        for(int i = 0; i < all_set; i++){
            vector<int> item;
            for(int j = 0; j < nums.size(); j++){
                //如果i的第j位为1，说明，有这一位所代表的元素。
                // （1 << j）第j位为1，其他位为0。
                // i & (1 << j)， i 这个数中，j这一位是不是为1。（i中是否包含这个元素）
                if(i & (1 << j)){
                    item.push_back(nums[j]);
                }
            }
            //将该子集放入集合中。
            result.push_back(item);
            item.clear();
        }
        return result;
    }
};