经典NP问题——子集问题

Leetcode刷题
留言

枚举子集问题毫无疑问是一个NP问题。对于这个问题一般两种解法，一种是利用位运算巧妙地进行枚举，另一种是利用递归进行枚举

78 子集

题目描述：

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：$nums = [1,2,3]$
输出：$[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]$

示例 2：

输入：$nums = [0]$
输出：$[[],[0]]$

提示：

$1 <= nums.length <= 10$
$-10 <= nums[i] <= 10$
nums 中的所有元素互不相同

解法一 :位运算

核心思路

结合位运算，用一个n位的二进制数来表示一个子集中各元素的存在与否，每一位代表一个元素是否包含在子集中，正好也有$2^n$个不同大小的二进制数可以代表$2^n$个子集。

比如整数数组为$[1,2,3,4,5]$，我们用5位的二进制数代表1个子集，具体某一位为0还是1代表某个子集包含还是不包含这个元素。10101代表了子集[1,3,5],00000代表了子集$[]$，11111代表了子集$[1,2,3,4,5]$。

代码

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
class Solution{
public:
    vector<int> t;      //t容器，作用是存放每一个临时数组，放到ans里
    vector<vector<int>> ans;    //ans容器，结果

    vector<vector<int>> subsets(vector<int>& nums) {
        //取到给的nums的大小
        int n = nums.size();
        // 子集的数量为2^n个。这个循环就是为了生成这些子集
        // mask可以理解为二进制数，一个mask就是一个子集，1、0代表了子集中哪个数存在不存在
        for (int mask = 0; mask < (1 << n); ++mask) {
            // 清空临时容器
            t.clear();
            // 循环遍历nums
            for (int i = 0; i < n; ++i) {
                // mask是子集，1<<i可以代表某个数在的情况
                // 通过位与运算，如果mask和某个数与的结果为0 则说明这个数不在子集中，就不用加到临时容器里，否则就加进来。
                if (mask & (1 << i)) {
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
}

复杂度

时间复杂度：$O(n\times 2^n)$。一共 $2^n$个状态，每种状态需要$O(n)$的时间来构造子集。

空间复杂度：$O(n)$。即构造子集使用的临时数组$t$的空间代价。

解法二：递归

核心思路

枚举子集其实最核心的思想就是考虑子集对每个元素的取舍问题。当前元素的取舍都会产生两类不同的子集。所以另一个解法就是利用递归，对每个元素进行取舍，递归的进行接收某个元素或放弃某个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
public:
    vector<int> t;
    vector<vector<int>> ans;
    
    dfs(int pos,vector<int> &nums){
        if(pos==nums.size()){
            ans.push_back(t);
            return ;
    	}
        t.push_back(nums[pos]);
        dfs(pos+1,nums);
        t.pop_back();
        dfs(pos+1,nums);
    }
    vector<vector<int>> subsets(vector<int>& nums){
        dfs(0,nums);
        return ans;
    }
}

复杂度分析

时间复杂度：$O(n\times 2^n)$。一共 $2^n$个状态，每种状态需要$O(n)$的时间来构造子集。

空间复杂度：$O(n)$。即构造子集使用的临时数组$t$的空间代价是$O(n)$,递归时栈空间的代价为$O(n)$。

90 子集II

题目描述：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。子集可以按任意顺序返回解集。

示例 1：

输入：$nums = [1,2,2]$
输出：$[[],[1],[1,2],[1,2,2],[2],[2,2]]$

示例 2：

输入：$nums = [0]$
输出：$[[],[0]]$

提示：

$1 <= nums.length <= 10$
$-10 <= nums[i] <= 10$

解法一 :位运算

核心思路

子集II和子集这两道题相比而言，就是多出了重复元素这种情况。显然对于示例数组$[1,2,2]$而言第一个元素与第二个元素组成的子集$[1,2]$和第一个元素与第三个元素组成的子集$[1,2]$其实并没有区别，这也就是如果我们直接用子集I来做这道题的话显然就会出错误。

显然对于上述出现的这种情况，之所以出现重复子集，是因为第三种元素和第二种元素的重复，我们舍弃了第二种元素，却接收了第三种元素，结果上看我们没有舍弃第二种元素。那解决办法就显而易见：首先我们将数组变得有序，然后当我们在对每个元素进行取舍的时候，看看前一个元素是否和它相同且是否舍去——如果前一个元素已经决定舍弃这个元素，那么我们显然也应当舍去这个元素。

代码

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
class Solution{
public:
	vector<int> t;
    vector<vector<int>> ans;
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums){
        int n = nums.size();
        sort(nums.begin(),nums.end());
        for(int mask=0;mask<(1<<n);mask++){
            t.clear();
            bool flag=true;
            for(int i=0;i<n;i++){
                if(mask & (1<<i)){
                    // i!=0 因为第0位没有前面的位；nums[i]==nums[i-1] 相同元素； mask>>(i-1) mask的第i-1位 也就是前一位，&1==0 是否舍弃
                    if(i!=0 && nums[i]==nums[i-1] && mask>>(i-1)&1==0 ){		
                        flag=false;		//如果舍弃了，我们也要舍弃这个选择。
                        break;
                    }
                    t.push_bcak(nums[i]);
                }
            }
            if(flag)		// 
	            ans.push_back(t);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n \times 2^n)$，其中 n 是数组$nums $的长度。排序的时间复杂度为 $O(nlogn)$。一共 $2^n$个状态，每种状态需要$O(n)$\ 的时间来构造子集，一共需要$O(n \times 2^n)$ 的时间来构造子集。由于在渐进意义上$ O(n \log n)$ 小于 $O(n \times 2^n)$，故总的时间复杂度为 $O(n \times 2^n)$

空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。

解法二： 递归

核心思路

和上述差不多，在递归的做法中就需要多传递一个参数来让当前函数判断是否和前一个函数相同。

代码

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<int> t;
    vector<vector<int>> ans;

    void dfs(bool choosePre, int cur, vector<int> &nums) {
        if (cur == nums.size()) {
            ans.push_back(t);
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return;
        }
        t.push_back(nums[cur]);
        dfs(true, cur + 1, nums);
        t.pop_back();
    }

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        dfs(false, 0, nums);
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n \times 2^n)$，其中 n 是数组$nums $的长度。排序的时间复杂度为 $O(nlogn)$。一共 $2^n$个状态，每种状态需要$O(n)$\ 的时间来构造子集，一共需要$O(n \times 2^n)$ 的时间来构造子集。由于在渐进意义上$ O(n \log n)$ 小于 $O(n \times 2^n)$，故总的时间复杂度为 $O(n \times 2^n)$

空间复杂度：O(n)。即构造子集使用的临时数组$t$的空间代价是$O(n)$,递归时栈空间的代价为$O(n)$。