78. 子集

题意

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂

集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

难度

中等

示例

示例 1：

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

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

分析 1

这题很容易想到的一个解法，就是先枚举子集的大小，再按照大小找出所有的子集，但是

这样子太麻烦了，代码也会非常冗长。我们来观察子集的数量公式。

按照刚刚的想法，我们可以得出子集数量 tot 和 nums 的长度 n 的一个关系式：

$ = ^{i=n}{i=0}{C^{i}{n}} $

再来观察一下，按照这个公式计算出来的 tot

n = 0 : tot = 1

n = 1 : tot = 1 + 1 = 2

n = 2 : tot = 1 + 2 + 1 = 4

n = 3 : tot = 1 + 3 + 3 + 1 = 8

n = 4 : tot = 1 + 4 + 6 + 4 + 1 = 16

...

咦，怎么有点杨辉三角的影子？

是的，没错，我们得出了这样一个结论：

$ = 2^{n} $

那既然子集的总数是 2 的 n 次方，很容易让我们联想到一种新的枚举方式——二进制枚

举！

我们知道，$ 0-(2^{n}-1) $里面，每个数字都不一样，自然，每个数字的二进制表示也是

不一样的，如果我们能把每个数字的二进制位上的`0`和`1`分别表示该位上的数字是**取**

还是**不取**，就能得到$ 2^{n} $种互不相同的取法。

然后只需要按照上述的二进制来选择，就可以快速获取所有的子集了。具体我们来看代码

实现：

class Solution {

// 最终结果存储

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {

// 遍历所有可能的子集组合（从 0 到 2^nums.length-1）

// 例如，如果 nums 长度为 3，则有 2^3=8 种可能的子集

for(int i = 0; i < (1 << nums.length); i++){

List<Integer> list = new ArrayList<>();

// 遍历 nums 的每一个数字，判断它是否应该出现在当前子集中

for(int j = 0; j < nums.length; j++){

// 使用位运算判断 j 位置的数字是否应该加入到子集中

// 如果 i 的第 j 位是 1，那么 nums[j]就应该在当前子集中

if((i & (1 << j)) != 0){

list.add(nums[j]);

}

}

// 添加当前子集到结果中

res.add(list);

}

return res;

}

}

我们在外层用一个循环，枚举了$ 0-(2^{n}-1) $次，然后再依次遍历 0-(n-1)，如果当前位

是 1 那么我们就将其加入 list 中，最后返回结果。

在上述的 LeetCode 题解中，我们正在检查数字 i 的第 j 位。为了创建一个只在第 j 位为 1

的掩码，我们使用 1 << j。例如，如果 j = 2，那么 1 << j 为 100，即数字 4。

现在，为了检查 i 的第 j 位是否为 1，我们可以使用与操作：i & (1 << j)。

• 如果结果是 0，那么 i 的第 j 位是 0。

• 如果结果不是 0，那么 i 的第 j 位是 1。

这就是为什么在题解中，我们使用 if ((i & (1 << j)) != 0)来判断 i 的第 j 位是否为 1，进

而确定 nums[j]是否应该包含在当前子集中的原因。

最后来看一下运行效率：

078.%E5%AD%90%E9%9B%86-20230914160520.png

分析 2

可能涉及到位运算对一些同学来说还是比较陌生的，我们再来看一种更加直观的解法——

回溯算法。

回溯算法是一个试错的方法，用于寻找所有（或某些）解决特定问题的方案。假如你尝试

构建一个解决方案，但你发现当前的解决方案无法成功，那就撤销最后一步（或多步），

然后在做其他尝试。简而言之，它涉及选择，执行和撤销。

回溯算法的主要特点包括：

1. 深度优先：回溯算法通常使用递归来解决问题，这意味着它使用深度优先策略来遍历

解决方案的空间。

2. 试错：如果某一路径不是正确的解决方案（或它不可能导致正确的解决方案），那么

算法会退回一步或多步，并尝试其他路径。

3. 方案空间树：你可以将可能的解决方案视为一棵树，其中每个节点是基于前一个选择

做出的一个选择。回溯算法遍历这棵树来找到解决方案，从根到叶子，尝试所有可能

的路径。

常见的问题，可以使用回溯算法来解决，包括但不限于：

• 组合问题（如从 n 个元素中选择 k 个元素的所有可能组合）。

• 排列问题（如所有可能的字母排列）。

• N 皇后问题。

• 图的着色问题。

• 解决数独。

回溯算法的基本结构通常如下：

function backtrack(path, choices):

if path is a solution:

save path

else:

for choice in choices:

make choice

backtrack(path with choice, updated choices)

undo choice

其中：

• path 是当前尝试的解决方案或部分解决方案。

• choices 是你还可以选择的选项或步骤。

回溯算法可以非常强大，但也可能是低效的，因为它可能需要探索解决方案空间的所有路

径。在实践中，许多优化策略（如剪枝）可以用来提高回溯算法的效率。

下面我们就用回溯算法来试一下：

1. 初始化一个空列表来存储所有的子集。

2. 使用递归方法从数组的第一个元素开始考虑每个元素：要么选择它，要么不选择它。

3. 如果达到数组的末尾，我们就把当前的子集添加到结果列表中。

4. 如果没有达到数组的末尾，我们先添加当前元素，然后进行递归，再回溯（即移除刚

才添加的元素），然后再进行递归。

下面是实现这个思路的代码：

class Solution {

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {

backtrack(nums, new ArrayList<>(), 0);

return res;

}

public void backtrack(int[] nums, List<Integer> current, int start) {

// 添加当前子集到结果

res.add(new ArrayList<>(current));

for (int i = start; i < nums.length; i++) {

// 选择当前数字

current.add(nums[i]);

// 向前探索

backtrack(nums, current, i + 1);

// 回溯：撤回刚才的选择，以考虑不选择当前数字的情况

current.remove(current.size() - 1);

}

}

}

解释：

• backtrack 方法开始时，首先将 current 当前子集添加到结果 res 中。

• 然后，我们考虑数组中的每一个数字。对于每一个数字，我们有两种选择：要么选择

它，要么跳过它。如果选择它，我们就把它添加到当前子集中，并继续向前递归；完

成递归后，我们需要回溯，即移除这个数字，并再次递归。

• 这样，我们能确保结果中的每一个子集都被考虑到。

来看一下运行效率：

078.%E5%AD%90%E9%9B%86-20230914160429.png

为了方便大家理解，我这里把代码加完整，直接以 ACM 的模式（带输入输出）来看一

下。

import java.util.ArrayList;

import java.util.List;

public class SubsetsSolution {

public static void main(String[] args) {

// 从命令行参数中解析输入

int[] nums = new int[args.length];

for (int i = 0; i < args.length; i++) {

nums[i] = Integer.parseInt(args[i]);

}

SubsetsSolution solution = new SubsetsSolution();

List<List<Integer>> result = solution.subsets(nums);

// 打印结果

for (List<Integer> subset : result) {

System.out.println(subset);

}

}

public List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> res = new ArrayList<>();

backtrack(nums, new ArrayList<>(), 0, res);

return res;

}

public void backtrack(int[] nums, List<Integer> current, int start,

List<List<Integer>> res) {

res.add(new ArrayList<>(current));

for (int i = start; i < nums.length; i++) {

current.add(nums[i]);

 backtrack(nums, current, i + 1, res);

current.remove(current.size() - 1);

}

}

}

OK，我们在 run configuration 中添加 123 参数，然后来看一下运行结果。

078.%E5%AD%90%E9%9B%86-20230914161520.png

结果如下：

[]

[1]

[1, 2]

[1, 2, 3]

[1, 3]

[2]

[2, 3]

[3]

总结

二进制枚举是我们在一些排列组合中需要统计确切的集合情况的时候经常遇到的一种解题

方法，通常能够使我们的代码更加简洁，并且能够节省一些没有必要的去重的问题。

力扣链接：https://leetcode.cn/problems/subsets/

更新: 2023-09-14 08:27:53

原文: https://www.yuque.com/itwanger/czfoq9/vr08q6