78. 子集
题目描述
输入整数数组 nums，其中元素各不相同。
返回 nums 的所有子集，也就是幂集，空集和整个数组本身都算。
结果里不能有重复的子集。子集之间的顺序不限。
示例 1
输入：nums = [1,2,3] 输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
解释：3 个元素共有 2^3 = 8 个子集。
示例 2
输入：nums = [0] 输出：[[],[0]]
解释：只有空集和 [0] 两个子集。
数据范围
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的元素两两不同。
解题思路
回溯枚举每个选择或跳过。
为什么正确
start 之后的元素才可继续选择。
复杂度分析
时间 O(n·2ⁿ)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def subsets(self,a):
out=[];p=[]
def f(s):
out.append(p[:])
for i in range(s,len(a)):p.append(a[i]);f(i+1);p.pop()
f(0);return outclass Solution {
private List<List<Integer>> out;
private List<Integer> p;
public List<List<Integer>> subsets(int[] nums) {
out = new ArrayList<>();
p = new ArrayList<>();
f(nums, 0);
return out;
}
private void f(int[] nums, int s) {
out.add(new ArrayList<>(p));
for (int i = s; i < nums.length; i++) {
p.add(nums[i]);
f(nums, i + 1);
p.remove(p.size() - 1);
}
}
}class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> out;
vector<int> p;
function<void(int)> f = [&](int s) {
out.push_back(p);
for (int i = s; i < (int)nums.size(); i++) {
p.push_back(nums[i]);
f(i + 1);
p.pop_back();
}
};
f(0);
return out;
}
};func subsets(nums []int) [][]int {
out := [][]int{}
p := []int{}
var f func(s int)
f = func(s int) {
out = append(out, append([]int{}, p...))
for i := s; i < len(nums); i++ {
p = append(p, nums[i])
f(i + 1)
p = p[:len(p)-1]
}
}
f(0)
return out
}var subsets = function(nums) {
const out = [], p = [];
const f = (s) => {
out.push([...p]);
for (let i = s; i < nums.length; i++) {
p.push(nums[i]);
f(i + 1);
p.pop();
}
};
f(0);
return out;
};function subsets(nums: number[]): number[][] {
const out: number[][] = [], p: number[] = [];
const f = (s: number): void => {
out.push([...p]);
for (let i = s; i < nums.length; i++) {
p.push(nums[i]);
f(i + 1);
p.pop();
}
};
f(0);
return out;
};其他解法
二进制枚举用整数直接对应子集，无递归、最短；回溯按“选或不选”逐层构造，能剪枝、能扩展到去重等变形题。
解法 2：二进制枚举 时间 O(n·2ⁿ)，空间 O(n)
n 个元素的每个子集都可以用一个 n 位二进制数表示：第 i 位是 1 表示选了 nums[i]。从 0 枚举到 2ⁿ-1，每个数字按位取出对应元素，就得到全部子集。
没有递归，代码非常短，适合 n ≤ 20 左右。缺点是不能像回溯那样在搜索中剪枝，处理第 90 题这种有重复元素的情况也不方便。
class Solution:
def subsets(self, nums):
n = len(nums)
out = []
for mask in range(1 << n):
out.append([nums[i] for i in range(n) if mask >> i & 1])
return outclass Solution {
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
List<List<Integer>> out = new ArrayList<>();
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> cur = new ArrayList<>();
for (int i = 0; i < n; i++)
if ((mask >> i & 1) == 1) cur.add(nums[i]);
out.add(cur);
}
return out;
}
}class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> out;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> cur;
for (int i = 0; i < n; i++)
if (mask >> i & 1) cur.push_back(nums[i]);
out.push_back(cur);
}
return out;
}
};func subsets(nums []int) [][]int {
n := len(nums)
out := [][]int{}
for mask := 0; mask < 1<<n; mask++ {
cur := []int{}
for i := 0; i < n; i++ {
if mask>>i&1 == 1 {
cur = append(cur, nums[i])
}
}
out = append(out, cur)
}
return out
}var subsets = function(nums) {
const n = nums.length;
const out = [];
for (let mask = 0; mask < (1 << n); mask++) {
const cur = [];
for (let i = 0; i < n; i++)
if (mask >> i & 1) cur.push(nums[i]);
out.push(cur);
}
return out;
};function subsets(nums: number[]): number[][] {
const n = nums.length;
const out: number[][] = [];
for (let mask = 0; mask < (1 << n); mask++) {
const cur: number[] = [];
for (let i = 0; i < n; i++)
if (mask >> i & 1) cur.push(nums[i]);
out.push(cur);
}
return out;
}