外观
12 - 回溯算法:排列组合、撤销选择与剪枝
前置阅读:11 - 递归、调用栈与问题缩减、13 - 二叉树遍历与层级结构。
状态缓存与最优子问题见21 - 动态规划的状态与转移,位掩码状态见25 - 位运算与状态压缩。
摘要
给定一组候选值,怎样找出和为目标值的所有组合?选完一个值后,还要继续尝试后续候选;这条路径处理完,再退回来尝试另一条。回溯用“选择、递归、撤销”组织这样的枚举过程。
本文先解释搜索树和路径状态,再用组合求和、子集与排列说明候选范围和答案收集时机,最后讨论去重、剪枝及重复状态的处理。
1. 通用框架
**搜索树(也称决策树)**是对选择过程的抽象:根节点表示还没有选择,每条边表示一次选择,节点表示已经做出的选择及剩余约束。它不一定是代码中实际创建的树。路径是从根走到当前节点的一串选择,通常用列表 path 保存。
回溯按深度优先的方式探索这棵树:先沿一条路径继续选择,当前分支处理完后返回,再尝试同一层的其他候选。一次调用需要知道当前路径、还能选哪些候选,以及还剩什么约束。
收集答案是保存符合题意的当前路径,停止搜索是不再向下扩展当前分支,两者不一定同时发生。本文的组合求和在剩余目标为 0 时收集并返回,因为继续添加正整数会超过目标;全排列在所有位置都已选用时收集并返回,因为没有未用位置;子集在每个节点收集后仍继续选择,直到该节点的候选全部处理完才返回。无法满足约束的分支也可以直接停止,不收集答案。
text
选择一个候选
-> 修改路径和状态
-> 递归进入下一层
-> 撤销选择2. 组合求和示例
递归返回会恢复调用位置,却不会自动恢复共享列表。比如路径从 [1] 变成 [1, 2],探索完这个分支后,必须删掉最后的 2,恢复为 [1],才能继续尝试 [1, 3]。其他共享状态也要一起恢复。
下面是需放入 Java 类中的局部方法,枚举和为目标值的组合,每个数组位置最多使用一次。调用方须保证:values 非 null、按升序排列且元素均为正整数,目标值非负,列表参数非 null。代码没有排序或输入校验;若要求按值得到唯一组合,还需第 4 节的去重逻辑。
初次调用传入 start = 0、remain = 目标值、空的 path 和空的 result。start 是本层候选的起始下标,remain 表示距离目标还差多少。
java
static void search(
int[] values,
int start,
int remain,
java.util.List<Integer> path,
java.util.List<java.util.List<Integer>> result
) {
if (remain == 0) {
result.add(new java.util.ArrayList<>(path));
return;
}
for (int i = start; i < values.length; i++) {
if (values[i] > remain) break; // 已排序,可剪枝
path.add(values[i]);
search(values, i + 1, remain - values[i], path, result);
path.remove(path.size() - 1); // 撤销
}
}选择下标 i 后,下一层从 i + 1 开始,因此不会再次使用该位置,也不会反过来选择更早的位置。remain 减去当前值,后续选择只需补足剩余目标;下标每次向后推进,有限数组最终会耗尽候选。remain == 0 时收集答案并返回。
以 values = [1, 2, 3]、目标值为 3 手工推演:先选 1,再选 2,收集 [1, 2];返回并撤销后,继续尝试其他候选,最终还会收集 [3]。这是预期结果,不是运行记录。
结果必须复制路径:new ArrayList<>(path) 创建独立列表,保存当前内容。若直接保存同一个 path 引用,后续撤销会同时改变已收集的答案,搜索结束时这些引用可能都指向空列表。
3. 排列、组合和子集
先确定“什么算一个答案”,再决定搜索规则。以互不相同的候选为例:
- 排列:
[1, 2]与[2, 1]不同。每层检查所有下标,用used[]记录当前路径已用位置;全排列在路径长度等于输入长度时收集并返回。 - 组合:
[1, 2]与[2, 1]相同。下一层只选当前下标之后的位置,用start避免因选择顺序不同而重复;达到指定个数或目标和时收集。 - 子集:不要求选满,也不要求达到目标和。同样只向后选,但每个搜索节点都收集,包括代表空集的根节点;收集后继续扩展,直到当前调用的候选全部处理完才返回。
4. 去重
如果答案按值区分,输入 [1, 1, 2] 的两个 1 就可能生成相同答案。同一搜索层指当前调用的循环:已有路径不变,只是在尝试下一步的不同候选。对组合或子集,先排序,让相同值相邻,再在该循环中加入下面的局部条件:
java
if (i > start && values[i] == values[i - 1]) continue;i > start 保留本层的第一个候选,只跳过后续相同值。根节点只用第一个 1 开启分支;进入已选一个 1 的下一层后,第二个 1 是该层的首个候选,仍可选出 [1, 1]。
“同层去重”避免重复答案;“同一路径不能重复使用”限制一个下标只能用一次。两个相同值可能来自不同下标,不能用禁止重复值代替禁止重复下标。第 2 节代码尚未加入此条件。
若要求包含重复元素数组的唯一排列,需要同时排序并使用:
java
if (used[i]) continue;
if (i > 0 && values[i] == values[i - 1] && !used[i - 1]) continue;used[] 在选择前设为 true,递归返回后恢复为 false。第一个条件禁止再次使用同一下标;第二个条件规定:前一个相同值尚未使用时,先由它代表本层的选择,跳过当前值。前一个相同值已在路径中时,当前值来自另一个下标,可以继续选择。这样既避免交换相同值产生重复排列,又保留包含多个相同值的合法路径。
5. 完整可运行示例:子集与排列
下面的完整类对应文件名 BacktrackingDemo.java,包含 main 入口。输入数组须非 null;按值枚举唯一答案时,本例要求元素互不相同,因为代码没有排序或去重。两个方法都不修改输入数组。
subset 在进入每个节点时收集路径,然后继续执行候选循环;perm 只有选满所有位置时才收集并立即返回。排列返回后既要删除路径末尾元素,也要恢复 used[i],否则下一分支会误以为该位置仍被占用。
java
import java.util.*;
/**
* 可运行示例:回溯算法:排列组合、撤销选择与剪枝。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class BacktrackingDemo {
static List<List<Integer>> subsets(int[] a) {
List<List<Integer>> out = new ArrayList<>();
subset(a, 0, new ArrayList<>(), out);
return out;
}
static void subset(
int[] a,
int start,
List<Integer> path,
List<List<Integer>> out
) {
// 子集问题中,搜索树上的每个节点都代表一个答案。
out.add(new ArrayList<>(path));
for (int i = start; i < a.length; i++) {
path.add(a[i]);
// 下一层只从 i+1 开始,防止重复使用此前位置。
subset(a, i + 1, path, out);
// 撤销本轮选择,恢复调用前状态。
path.remove(path.size() - 1);
}
}
static List<List<Integer>> permutations(int[] a) {
List<List<Integer>> out = new ArrayList<>();
perm(a, new boolean[a.length], new ArrayList<>(), out);
return out;
}
static void perm(
int[] a,
boolean[] used,
List<Integer> path,
List<List<Integer>> out
) {
if (path.size() == a.length) {
// 必须保存副本,path 随回溯仍会变化。
out.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < a.length; i++) {
if (used[i]) continue;
// 排列关注顺序;used 保证同一路径中每个下标只使用一次。
used[i] = true;
path.add(a[i]);
perm(a, used, path, out);
path.remove(path.size() - 1);
used[i] = false;
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
System.out.println(subsets(new int[] { 1, 2, 3 }));
System.out.println(permutations(new int[] { 1, 2, 3 }));
}
}搜索树与复杂度
[1,2,3] 的排列树第一层有 3 个选择、第二层有 2 个、第三层有 1 个,共 3! 个叶子。n! 表示从 1 到 n 的整数乘积。对 n 个互不相同的元素,共有 n! 个全排列,每个答案都要复制长度为 n 的路径。
Ω 表示渐近下界,即规模增长时至少需要的计算量;O 表示渐近上界,即规模增长时计算量不超过的增长量级。两者都忽略常数倍,并讨论输入规模足够大时的情况。因此,仅生成并保存全部排列就有 Ω(n·n!) 的时间下界,本例总体时间为 O(n·n!)。子集共有 2^n 个,计入路径复制后,本例时间为 O(n·2^n)(n >= 1)。
两者的路径、使用标记和递归栈占用 O(n) 辅助空间,不包括结果列表。结果本身分别需要 O(n·n!) 和 O(n·2^n) 空间,因此枚举所有答案仍受输出规模限制。
去重是删除等价答案,剪枝是排除不可能成功的分支。二者必须有约束依据;例如“候选大于剩余目标就停止”只有在候选已排序且非负时才成立。
main 只演示 [1, 2, 3],没有覆盖代码注释所说的边界输入。按手工推演,子集方法预期得到 8 个结果,排列方法预期得到 6 个结果。建议补测空数组和重复值;空数组在这两个方法中都预期得到只含空路径的结果 [[]]。组合求和还应测试无解和目标为 0,后者在第 2 节实现中返回空组合。
6. 剪枝必须保持正确性
只有能证明当前分支不可能产生有效或更优答案时才能剪枝。例如候选均为正数且已排序时,当前值大于剩余目标,后续更大值也不可能成功。
若存在负数,该剪枝就不成立。
第 2 节使用 break 而不是 continue,是因为排序保证后续候选不会更小;候选非负时,一旦当前值超过剩余目标,继续添加候选也无法补回差额。非负性支持这条剪枝规则,而求和示例采用更严格的正整数前提,避免达到目标后继续添加零值产生其他组合的语义问题。
剪枝常见的依据有三类:
- 可行性界:证明剩余选择无法满足约束,例如上述剩余目标判断。
- 最优性界:只求最优答案时,证明该分支即使达到最好情况,也不能改善已知答案。若要保留所有并列最优答案,还要谨慎处理相等的情况。
- 对称性:证明两个分支只会生成等价答案,于是保留一个代表;第 4 节的同层去重就是这种做法。
枚举全部合法答案时,剪枝必须保留所有按题意区分的答案;只求最优值时,则要保留求得最优值所需的分支。优化前后应在小规模输入上做差分测试,即比较剪枝版与未剪枝版的结果。再比较搜索节点数量,确认减少了多少搜索工作;节点减少不等于已经测得耗时提升。
7. 何时应改用动态规划
等价状态指后续允许的选择和待求答案相同,即使到达它们的路径不同,也可以复用后续计算。例如,候选数组固定且每个位置最多使用一次时,组合求和的后续计数可考虑用 (start, remain) 描述;排列还需知道哪些下标已使用,不能只用路径长度作为状态。
大量路径到达等价状态时,纯回溯会重复计算。记忆化是在递归中缓存状态的答案,再次遇到时直接复用;自底向上计算则先算较小状态,再按依赖顺序组合它们。使用前要确认状态信息充分,并且状态数量和保存成本可接受。
回溯适合枚举具体路径;动态规划常用于复用子问题的最优值或计数。两者可以组合:缓存可行性、计数或最优值,再保留选择记录恢复答案。但需要输出所有组合时,不能仅因某个状态以前访问过,就跳过从新路径到达它的搜索,否则可能漏掉带有不同前缀的答案。缓存也不能消除输出所有答案本身的成本。
8. 容易踩的坑
- 递归后忘记撤销状态。
- 保存路径引用而不是副本。
- 把组合问题写成排列,产生大量重复结果。
- 剪枝依赖“全为正数”,代码却未校验输入。
- 搜索空间巨大却没有输入上限。
9. 总结
回溯通过维护一条可撤销的决策路径,系统枚举搜索空间。
- 选择、递归、撤销是回溯的基本闭环。
- 排列、组合和子集的差异来自候选范围与答案收集时机。
- 剪枝必须有可证明的条件,否则是在删除可能正确的答案。
重复状态较多时继续阅读动态规划的状态与转移;小规模集合状态可结合位运算与状态压缩。