有三个可选项目 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); }}循环里的三行对应整个回溯过程:
path.add(values[i]):尝试选择当前元素。search(...):在这个选择之上继续探索。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.javajava 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,结果应为 []。本篇原始代码只生成全部子集,这些规则需要你在练习版中实现。
下一篇的动态规划与最少硬币会遇到另一类需求:我们只想得到最优结果,而且不同选择会反复走到相同的子问题。
If this article helped you, please share it with others!
Some information may be outdated






