subSets

发表于 | 分类于 | 浏览 次
  1. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题目链接

方法一:枚举

一次处理一位，循环处理每一位即可．注意，在枚举各位之前必须将数组排序，保证相等元素相邻。 比如对于题目中给的例子 [1,2,3] 来说，最开始是空集，接下来首先处理第一位1，于是就在空集上加1，为 [1]，现在我们有两个子集 [] 和 [1]．然后来处理2，我们在之前的子集基础上，每个都加个2，可以分别得到 [2]，[1, 2]，那么现在所有的子集合为 [], [1], [2], [1, 2]，用同样的方法处理3可得 [3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back({});
        for(int i=0;i<nums.size();++i){
            int size = res.size();
            for(int j=0;j<size;++j){
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
            }
        }
        return res;
    }
}

方法二: 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        subsetsCore(0, nums, tmp, res);
        return res;
    }
    
    void subsetsCore(int pos, vector<int>& nums,vector<int> &tmp, vector<vector<int>> &res){
        res.push_back(tmp);
        for(int i=pos;i<nums.size();++i){
            tmp.push_back(nums[i]);
            subsetsCore(i+1, nums, tmp, res);
            tmp.pop_back();
        }
    }
};

依次形成以索引0处开头的所有子集、以索引1处的元素开头的所有子集，直到以最后一个元素开头的子集。

方法三: 位操作

思路：为数组中所有的数分配一个状态，状态0表示这个数不在子集中出现，状态1则表示这个数在子集中出现．对于一个长度为n的数组，每个数组都有出现和不出现两种情况，所以共有2n种情况．因此，把1 - 2n-1-1转换为对应的二进制形式，再将这个二进制字符串转换成子数组即可．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int maxVal = 1 << nums.size();
        for(int k=0;k<maxVal;++k){
            vector<int> tmp = convertIntToSet(nums, k);
            res.push_back(tmp);
        }
        return res;
    }
    
    vector<int> convertIntToSet(vector<int>& nums, int k){
        vector<int> sub;
        int index = 0;
        for(int i=k;i>0;i>>=1){
            if((i&1)==1){
                sub.push_back(nums[index]);
            }
            ++index;
        }
        return sub;
    }
};

Subsets II

题目链接

方法一:枚举

思路，对于数组nums: [1,2,2,3]
最初，结果集res中只有空集，即res = [[]]
第1轮，将元素1加入到结果集中：res = [[], [1]]
第2轮，将元素2加入到结果集中：res= [[],[1], [2], [1,2]]
第3轮，接下来又是元素2，如果将复制之前的每个子集，再在复制的子集中加入元素2就会出现重复。即
res = [[], [1], [2], [1,2], [2], [1,2], [2, 2], [1,2,2]]，其中红色的两个集合是重复的。即我们只能在已经出现元素2的集合中加入第二个2，形成不重复的子集。也就是说，只需要在加入了索引1处的元素2的两个子集中加入索引2处的元素2。可以在第2轮确定索引1处的元素加入到了几个子集（假设为n）中。第3轮只往这n个子集（位于结果集res的末尾处）中加入重复的元素2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        res.push_back({});
        int pre = 1;
        for(int i=0;i<nums.size();++i){
            int size = res.size();
            
            // 如果上一个元素与当前元素不同，则说明可以将当前元素加入到所有子集中
            if(i && nums[i] != nums[i-1]){
                pre = size;
            }
            for(int j=size-pre;j<size;++j){
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
            }
        }
        return res;
    }
};

方法二: 回溯

如何在回溯过程中消除重复元素的影响？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> tmp;
        subsetsWithDupCore(nums, res, tmp, 0);
        return res;
    }
    
    void subsetsWithDupCore(vector<int>& nums, vector<vector<int>>& res, vector<int>& tmp, int pos){
        res.push_back(tmp);
        for(int i=pos;i<nums.size();++i){
            tmp.push_back(nums[i]);
            subsetsWithDupCore(nums, res, tmp, i + 1);
            tmp.pop_back();
            while(i < nums.size() -1 && nums[i] == nums[i+1]){
                ++i;
            }
        }
    }
};

参考文献

[1] Subsets 子集合: https://www.cnblogs.com/grandyang/p/4309345.html
[2] 含有重复元素的subsets子集: https://www.cnblogs.com/grandyang/p/4310964.html