mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
2083 words
5 minutes
算法入门(七):用全部子集理解回溯
2026-10-21

有三个可选项目 1、2、3,你可以一个都不选,也可以选择其中任意几个。现在需要列出全部选择,例如 []、[1]、[1, 2]、[2, 3]。

只写三层循环可以处理三个项目,但输入变成五个、十个时,循环层数就要跟着修改。我们需要一种能够随着输入规模自然展开的写法。

本篇用生成全部子集学习回溯:做出一个选择,继续探索,回来以后撤销这个选择,再尝试下一条路。使用 Java 17 及以上版本,完整学习顺序见系列目录。阅读前应熟悉前面介绍的递归调用。

一、先把“全部”说清楚#

输入为互不相同的整数数组:

[1, 2, 3]

每个元素可以选,也可以不选,每个位置最多使用一次。结果应该包含八个子集:

[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

结果的排列顺序不影响正确性。[1, 2] 与 [2, 1] 表示同一个选择,不应因为顺序不同就计算两遍。空集 [] 表示什么都不选,也是合法结果。

我们约定输入元素互异。若输入 [1, 1],两个位置虽不同,却可能得到相同的数值列表;本篇代码没有对这种情况去重。这个前提要在使用算法前确认。

二、把过程想成逐步延长一条路径#

准备一个列表 path,记录目前选了什么。开始时它为空。

如果选择 1,路径变成 [1];继续选择 2,得到 [1, 2];再选择 3,得到 [1, 2, 3]。这条路已经走到底,于是撤销 3,回到 [1, 2]。

从这一层返回以后,再撤销 2,回到 [1]。现在可以尝试直接选 3,得到 [1, 3]。这样反复深入与返回,就能覆盖不同组合。

[]
├── [1]
│ ├── [1, 2]
│ │ └── [1, 2, 3]
│ └── [1, 3]
├── [2]
│ └── [2, 3]
└── [3]

这是一棵搜索树。它描述算法可能经过的状态,不要求真的在内存里建立一组树节点。递归调用负责记住当前在哪一层,path 负责记住这一条分支上已经作出的选择。

在这个问题中,搜索树上的每个节点都对应一个合法子集,因此每次进入一个状态时,都可以把当前路径保存到结果。

三、start 让每个组合只走一次#

还剩一个关键问题:选了 2 以后,为什么不能再选前面的 1?

我们用 start 表示“本层允许从哪个下标开始继续选择”。如果本次选的是下标 i,下一层就从 i + 1 开始。这样路径上的下标始终递增。

例如,在 [1, 2, 3] 中,选择下标 1 的数值 2 以后,后续只能选择下标 2 的数值 3。不会回到下标 0,也不会再次使用下标 1。

这个约束同时解决两件事:同一个位置不会被重复使用,同一组选中的位置不会以不同顺序重复生成。数组本身不必按数值排序,递增的是下标。

可以这样描述递归函数的职责:

已经选出的内容保存在 path 中;把从 start 开始还能形成的所有扩展加入结果。

每次调用前后都保持这个含义,比记住一个固定模板更有帮助。

四、代码中的三步:选择、递归、撤销#

下面是完整示例的核心方法,省略类定义与 ArrayList、List 的导入:

public static List<List<Integer>> subsets(int[] values) {
if (values == null) {
throw new IllegalArgumentException("values must not be null");
}
List<List<Integer>> result = new ArrayList<>();
search(values, 0, new ArrayList<>(), result);
return result;
}
private static void search(int[] values, int start,
List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path));
for (int i = start; i < values.length; i++) {
path.add(values[i]);
search(values, i + 1, path, result);
path.remove(path.size() - 1);
}
}

循环里的三行对应整个回溯过程:

  1. path.add(values[i]):尝试选择当前元素。
  2. search(...):在这个选择之上继续探索。
  3. path.remove(...):探索完成后恢复进入该分支前的路径。

“撤销”不是从已经保存的结果中删除答案,而是恢复工作中的路径,让下一条分支从同样的起点开始。

这里没有单独写 if (start == values.length) return。当 start 到达数组末尾时,当前路径被保存,for 条件不成立,函数自然返回。问题规模通过 i + 1 不断缩小,不会无限递归。

五、手动跟踪一次返回过程#

为了专注看清返回,先输入 [1, 2]:

动作当前路径已保存结果
进入最外层[][[]]
选择 1,进入下一层[1][[], [1]]
选择 2,进入下一层[1, 2][[], [1], [1, 2]]
返回,撤销 2[1]不变
返回最外层,撤销 1[]不变
最外层选择 2[2][[], [1], [1, 2], [2]]
返回,撤销 2[]不变

内层函数返回后,执行会从调用语句的下一行继续。因此,remove 恰好发生在“这次选择的所有后续可能性都探索完”之后。

可以在三行操作附近临时打印 path,观察进入和返回;但输入较大时日志也会指数增长,调试时使用两三个元素就足够了。

六、为什么保存结果时要复制路径#

这一行不能随意简化:

result.add(new ArrayList<>(path));

它保存当前路径的一份快照。后面继续增加或删除 path 中的元素,已经保存的列表不会跟着改变。

如果写成 result.add(path),结果里保存的是同一个可变列表的引用。回溯结束时,path 被撤销回空列表,多个答案也会一起看起来变成空列表。

new ArrayList<>(path) 复制了列表结构。这里元素是 Integer,不可变,足以满足需求;如果路径里保存的是仍会被修改的复杂对象,还要进一步考虑对象内容是否也需要复制。

空输入同样能按这套规则处理:第一次进入时保存空路径,随后循环不执行,返回 [[]]。它与没有任何结果的 [] 含义不同。

七、运行与复杂度#

下载完整 Backtracking.java,或者下载系列源码包。在文件所在目录运行:

javac -encoding UTF-8 Backtracking.java
java Backtracking

预期输出:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
[[]]

对于 n 个互异元素,每个都有选与不选两种状态,因此一共有 2^n 个子集。只要题目要求返回全部子集,就必须承担这么多结果的输出成本。

保存一个子集还需要复制其中的元素。对于 n ≥ 1,所有子集里一共包含 n × 2^(n-1) 个元素,所以生成并保存全部结果的时间复杂度是 O(n × 2^n),返回结果占用的空间也是 O(n × 2^n)。

只计算工作中的路径和递归栈,最大深度为 n,辅助空间是 O(n)。分析时要说明是否计入返回结果,否则“空间 O(n)”会让读者低估实际内存需求。

剪枝是提前排除不可能满足要求的分支。本题要求全部子集,每个分支都有答案,不能把它们随意删掉;也不能期待加上回溯框架就把指数级输出变成线性。

八、练习:只返回恰好选两个元素的组合#

输入仍为 [1, 2, 3],要求改为恰好选两个,预期结果是:

[[1, 2], [1, 3], [2, 3]]

可以把目标数量作为 k 传入:当 path.size() == k 时保存快照并返回;未达到数量时继续选择。注意,此时不再是一进入函数就无条件保存路径。

进一步观察:如果“已选数量 + 剩余可选数量”仍然小于 k,这条分支已经不可能凑够,可以提前返回。这才是与具体目标相关的剪枝条件。

验收时加入 k = 0,结果应为 [[]];加入 k > n,结果应为 []。本篇原始代码只生成全部子集,这些规则需要你在练习版中实现。

下一篇的动态规划与最少硬币会遇到另一类需求:我们只想得到最优结果,而且不同选择会反复走到相同的子问题。

Share

If this article helped you, please share it with others!

算法入门(七):用全部子集理解回溯
https://mizuki.mysqil.com/posts/algorithm-07-backtracking/
Author
梦幻晨风
Published at
2026-10-21
License
CC BY-NC-SA 4.0

Some information may be outdated

Table of Contents