欢迎访问LeetCode题解合集
题目描述:
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
- $1 \le nums.length \le 10$
- $-10 \le nums[i] \le 10$
nums
中的所有元素 互不相同
题解:
法一:
递归实现子集枚举。
参考 组合 方法一 中的第二种写法,每个元素面临 选择 与 不选择 两个状态。
时间复杂度:$O(n * 2^n)$
额外空间复杂度:$O(n)$
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs( int p, vector<int>& nums ) {
if ( p >= nums.size() ) {
ret.emplace_back( path );
return;
}
dfs( p + 1, nums );
path.emplace_back( nums[p] );
dfs( p + 1, nums );
path.pop_back();
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs( 0, nums );
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:10.6MB,击败:21.04%
*/
空间有点爆炸,主要是递归消耗。
法二:
n
个不同元素的集合共有 $2^n$ 个子集,考虑使用 0~(1<<n)-1
共 $2^n$ 个数分别表示这 $2^n$ 个子集。
比如 0000
表示空集, 1111
表示全集。
从 0
到 (1<<n)-1
枚举所有子集,假设这个数的二进制表示的第 i
位是1,则表示该子集包含第 i
个数,否则表示不包含。
时间复杂度:$O(n * 2^n)$
额外空间复杂度:$O(n)$
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums) {
int n = 1 << nums.size();
for ( int i = 0; i < n; ++i ) {
path.clear();
for ( int j = 0; j < nums.size(); ++j ) {
if ( i >> j & 1 ) path.push_back( move(nums[j]) );
}
ret.push_back( move(path) );
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:6.9MB,击败:94.20%
*/
不使用递归明显内存消耗小很多。