从循环枚举到全排列回溯：配对约束题的Java实现与剪枝

前阵子帮A同学看一道Java经典题，题目是给两组对象做配对，满足若干约束，要求列出所有可行方案。A同学一开始用多重循环枚举，代码写了六层，变量名从i排到q，改一个条件要动好几处；我建议他换成全排列回溯，结果代码短了一半，扩展性也好了。这篇就围绕从循环枚举到全排列回溯的演进，把配对约束这类题的拆解思路讲清楚。下面涉及的操作步骤、参数选择和优化手段，除题目本身给出的条件外，都是基于常见刷题和项目实践做的合理补全，你按自己的场景调整即可。适合刚接触回溯、写得出递归却总在“恢复现场”上翻车的人，也适合想搞清楚暴力枚举和搜索剪枝边界的读者。

1. 先把问题说透：配对约束到底在约束什么

1.1 从生活场景抽象成约束模型

配对约束听起来抽象，落到生活里就是“谁能和谁搭伙”的问题。比如几项任务要分给几个人，每个人只能领一项，某些人因为技能不匹配不能做某些任务；再比如座位安排，若干人坐若干位置，有人不能挨着某些位置，有人有偏好。把人和任务分别看作两个集合，配对就是建立一一对应关系：每个人恰好选一个任务，每个任务恰好被一个人选。约束通常体现为一个二维矩阵conflict[i][j]，表示第i个人不能配第j个任务，或者反过来表示允许。这个矩阵不一定对称，因为“人不能做任务”和“任务不适合人”在语义上是一回事，但如果是两组同类对象配对，比如男生女生配对，约束往往是对称的。

从算法视角看，这类问题可以归为排列生成加可行性过滤。全排列生成的是“每个位置放一个元素”的所有顺序，而配对问题里“位置”就是一组对象，“元素”就是另一组对象。生成一个排列，就相当于给每个位置分配了一个对象，天然满足“一个对象只用一次”的硬约束。剩下的软约束、硬约束，都在生成过程中用条件判断筛掉。理解这一点很关键：配对约束不是独立于排列之外的另一个问题，它就是在排列的每个位置上加过滤条件。很多初学者把配对和排列分开想，代码就越写越散。

这里要区分两种目标：如果只求“最多能配多少对”，那是二分图最大匹配问题，用匈牙利算法或者网络流更合适；如果要求“列出所有可行配对方案”，或者方案数量不多、需要按某种顺序输出，那全排列回溯更直接。题目里说的“搞定配对约束”，多数场景是后者。先把目标定清楚，再谈选型，不然容易拿最大匹配的算法去解枚举所有方案的问题，方向就偏了。

1.2 为什么暴力循环枚举很快就不够用

循环枚举的思路很直白：有几个人就写几层循环，每层循环选一个任务，选过的用条件跳过。四个人配四个任务，四层循环还能接受；五个人配五个任务，五层循环也勉强能看；到了八个人，八层循环的缩进已经像楼梯，变量名不够用，条件判断越写越长。更麻烦的是人数不固定。实际题目里n经常作为输入给出，循环层数没法在编译期确定，只能写死一个上限或者改用递归。写死上限意味着扩展性差，题目稍微变一下就要重写。

复杂度上，循环枚举和全排列是同一量级。n个人全排列有n!种，循环枚举如果不加剪枝，每层都从0到n-1试一遍，再判断是否重复，实际尝试次数是n的n次方级别。比如n=8，8的8次方是1600多万，而8!是40320，差了将近400倍。循环枚举里那些“选过就跳过”的判断，本质上是在运行时排除重复，而全排列回溯用used数组把“选过”变成状态，试错次数直接降到n!量级。这个差距在小n时看不出来，n到9、10就会非常明显。n=10时10!是362万，10的10次方是100亿，完全不是一个世界。

还有一个隐蔽问题：循环枚举的剪枝位置很别扭。假设第一个人和第3个任务冲突，你只能在最内层或者每层开头判断，但循环结构是扁平的，想把“当前部分分配已经不可行”这种信息提前传下去很困难。回溯的递归结构天然支持“走一步看一步”，每一层都能拿到前面所有选择的结果，剪枝条件可以写得很自然。所以循环枚举适合n≤4、约束极少、代码一次性写完不再改的场景；一旦n可变或者约束复杂，就该考虑换方案。我一般把4层作为心理阈值，超过4层或者题目输入n，直接上回溯，不纠结。

1.3 全排列回溯为什么能接住这个问题

全排列回溯的核心是递归树。树的每一层代表“给当前这个位置选一个元素”，路径上记录已经选过的元素，选择列表是还没被选过的元素。走到叶子节点，路径长度等于n，就是一个完整排列。配对问题把“位置”理解成第一组对象，“元素”理解成第二组对象，叶子节点就是一个完整配对方案。递归深度等于n，每一层用一个循环尝试所有可选对象，选完标记，递归下去，回来撤销标记。这个结构把“一一对应”的硬约束直接编码进used数组，不需要在每层写一堆if (b == a || c == a || c == b)。

更关键的是，约束可以分层注入。第i个人选任务时，只需要检查conflict[i][task]，前面人的选择已经通过used数组排除了。如果还有“第i个人和第i-1个人不能选同一个任务”这种额外约束，也能在这一层拿到match[i-1]做判断。递归让上下文变得可用，这是循环枚举很难做到的。你可以把回溯理解成“带状态的深度优先搜索”，状态就是路径和已用集合。配对约束本质上是搜索空间上的过滤器，过滤器放在每一层选择之前，效率最高。

当然，全排列回溯不是银弹。它的搜索空间仍然是指数级，n=12以上即使剪枝也可能很慢，结果集本身也可能巨大。所以后面要讲剪枝、对称性去重、搜索顺序优化。但在n≤10、约束中等复杂的配对题里，回溯是性价比很高的选择：代码短、可读性好、容易加条件、容易调试。先把骨架写对，再谈优化，顺序不能反。

2. 循环枚举的写法与边界：小规模快糙猛可以，但别硬撑

2.1 固定层数循环的经典写法

先看一个四个人配四个任务的循环枚举版本。假设conflict[i][j]为true表示第i个人不能做第j个任务。四层循环，每层选一个任务，用前面的变量排除重复，再查冲突矩阵。代码大概是这样：

import java.util.Arrays; public class LoopEnum { static int n = 4; static boolean[][] conflict = new boolean[n][n]; public static void main(String[] args) { // 这里只是示例，实际按题目初始化冲突矩阵 int[] p = new int[n]; int count = 0; for (int a = 0; a < n; a++) { if (conflict[0][a]) continue; p[0] = a; for (int b = 0; b < n; b++) { if (b == a || conflict[1][b]) continue; p[1] = b; for (int c = 0; c < n; c++) { if (c == a || c == b || conflict[2][c]) continue; p[2] = c; for (int d = 0; d < n; d++) { if (d == a || d == b || d == c || conflict[3][d]) continue; p[3] = d; count++; System.out.println(Arrays.toString(p)); } } } } System.out.println("方案数：" + count); } }

这段代码能跑，逻辑也直白，但问题一眼可见：重复判断随着层数增加越来越长，第四层要判断三个变量是否相等。如果n变成5，你得再加一层，并且第五层的判断要写四个相等比较。每加一层，代码量几乎翻倍。变量名也不够用，a到d还能忍，到e、f、g就开始混乱。这种写法适合考试时快速拿分，或者题目明确n≤4且不会变。放在工程里，维护的人会很痛苦。

还有一个细节：循环枚举里结果数组p是复用的，每次赋值覆盖。如果要把所有方案存起来，得在叶子节点做拷贝，比如result.add(p.clone())，不能直接result.add(p)，否则最后全是同一个引用。这个问题在回溯里同样存在，后面会细说。循环枚举的另一个坑是初始化。p的每个位置在进入对应层之前可能残留上一次的值，虽然叶子节点会全部覆盖，但如果在循环中间提前打印或者做判断，可能读到脏数据。回溯里用path配合remove更干净，循环枚举则要自己保证每个位置在使用前被赋值。

2.2 循环枚举的优化：提前剪枝与对称去重

循环枚举不是完全不能优化。最常用的两招：一是把冲突判断提前，能在外层判断的不要拖到内层；二是利用对称性减少重复搜索。比如配对问题里，如果两组对象完全同质，交换两组得到的方案在某种意义上等价，可以固定第一组的第一个对象必须配第二组的第一个对象，把搜索空间砍一半。但循环枚举的固定层数结构让这种“固定”很别扭，你只能在外层加条件，内层就不好动态调整了。

提前剪枝的例子：如果第0个人可选的任务只有两个，你可以在第一层循环之前先算出一个可选列表，循环只遍历这个列表，而不是从0到n-1全扫一遍再判断。这样能减少无效迭代。但代码会变得更长，需要额外的数组和预处理。对于四层循环，收益不大；对于更多层，又回到“层数写死”的老问题。所以循环枚举的优化空间很有限，本质上是在一个不灵活的结构上打补丁。

对称去重也有坑。假设你固定第0个人选任务0，但题目可能根本不存在“第0个人配任务0”的可行解，这时候固定就漏解了。对称性剪枝的前提是“对称变换后的解仍然合法”，如果约束矩阵不对称，或者两组对象角色不同，固定某个配对可能直接排除掉所有可行解。所以用对称性之前，先确认问题是否真的对称。我见过有人在一道“人与任务”的题里固定“第一个人做第一个任务”，结果第一个任务恰好是第一个人不能做的，输出直接为空。这种错误不是算法错，是业务假设错。

2.3 什么时候该停手换方案

判断标准其实很简单：看n是不是输入，看约束会不会变，看代码要不要复用。n是输入，循环层数就没法固定，硬写上限就是给自己挖坑；约束会变，循环里的条件判断会膨胀；代码要复用，循环枚举几乎没有复用价值，每次都要重写。这三个问题里中一个，就该考虑回溯。如果n固定为3或4，约束就一两个，写完就扔，循环枚举反而更快，不用建递归、不用管理状态，调试也直观。

我自己的习惯是：先花两分钟评估，如果n≤4且题目明确不会扩展，写循环枚举；否则直接写回溯骨架。不要觉得回溯一定比循环高级，工具没有高低，只有合不合适。循环枚举在极小规模下的优势是“没有递归开销、没有状态恢复风险、一眼看到底”。回溯的优势是“结构统一、扩展性好、剪枝自然”。把循环枚举当成小规模的特化版本，把回溯当成通用版本，心里就清楚了。真正要避免的是“n已经到8了还在硬写八层循环”，那不是坚持，是给自己找麻烦。

3. 全排列回溯的核心骨架：把“恢复现场”刻进肌肉记忆

3.1 递归树长什么样：路径、选择列表、结束条件

回溯的递归树要先在脑子里画出来。以四个人配四个任务为例，根节点是“还没分配”，第一层有四个分支，分别表示第0个人选任务0、1、2、3。每个分支往下，第二层表示第1个人选剩下的三个任务，依此类推。叶子节点是第四个人选完最后一个任务，此时路径长度等于4，得到一个完整方案。树的深度是n，每一层的分支数逐层递减：n、n-1、n-2……所以叶子节点数量是n!。这个结构就是全排列的生成树，配对约束只是在某些分支上提前砍掉。

写回溯代码时，脑子里要同时装三样东西：路径、选择列表、结束条件。路径用match[]或者List<Integer> path记录已经做出的选择；选择列表是当前层还能选的对象，通常用used[]数组标记哪些已经被选；结束条件是路径长度等于n，此时收集结果并返回。这三样东西对应代码里的三个位置：递归参数、循环范围、递归出口。很多人写回溯喜欢把used数组当全局变量，路径也当全局变量，这没问题，但一定要在递归返回后撤销修改。全局变量加手动恢复，是回溯最容易出错的地方。

递归树的每一层对应一个“决策点”。在配对问题里，决策点是“第i个人选哪个任务”。如果你把决策点理解成“第j个任务分给谁”，树的结构会变，但方案总数不变。选择哪种视角会影响剪枝效率。通常建议选择“约束更多的一侧”作为决策层。比如人的可选任务很少，就以人为层；任务的可选人很少，就以任务为层。这个选择在后面讲搜索顺序时还会提到。先把基础骨架写对，再谈视角优化。

3.2 状态标记与恢复现场：used数组的用法

基础骨架长这样：

import java.util.ArrayList; import java.util.List; public class BacktrackPair { static int n = 5; static boolean[][] conflict = new boolean[n][n]; static int[] match = new int[n]; static boolean[] used = new boolean[n]; static int count = 0; static List<int[]> result = new ArrayList<>(); public static void main(String[] args) { // 按题目初始化 conflict backtrack(0); System.out.println("方案数：" + count); } static void backtrack(int person) { if (person == n) { count++; result.add(match.clone()); return; } for (int task = 0; task < n; task++) { if (used[task]) continue; if (conflict[person][task]) continue; used[task] = true; match[person] = task; backtrack(person + 1); used[task] = false; match[person] = -1; } } }

这段代码的关键在backtrack(person + 1)前后的三行：标记、赋值、递归、撤销。used[task] = true表示任务被占用，match[person] = task记录选择；递归返回后，used[task] = false和match[person] = -1把现场恢复原样，让当前层可以尝试下一个任务。如果漏掉撤销，会出现“第一个分支把任务全占了，后面的分支无任务可选”的现象，输出要么为空，要么方案数少得离谱。这个错误极其常见，因为代码在简单用例上可能碰巧能跑，一到复杂用例就暴露。

match[person] = -1不是必须的，因为下一次赋值会覆盖，但保留它有两个好处：一是调试时能看出当前位置是否已赋值，二是如果后续剪枝逻辑要读match的旧值，未重置可能读到脏数据。我倾向于保留，成本可以忽略。used数组的恢复是必须的，因为它是判断“任务是否被占用”的唯一依据。有人用match数组反过来判断任务是否被占用，遍历match看是否等于task，这样能省一个数组，但每层判断要从O(1)变成O(n)，不划算。used数组是典型的空间换时间，n不大时完全值得。

3.3 配对约束怎么塞进递归：冲突检测放在选择前

配对约束的检查位置很讲究。上面的代码在for循环里先判断used[task]，再判断conflict[person][task]，顺序可以互换，但都必须在“标记、递归”之前。如果放到递归之后，那就变成“先选再检查”，选了一个冲突的任务，递归下去才发现不行，白白展开一棵子树。剪枝的原则是“能早停就早停”，冲突检测放在选择之前，等于在分支产生之前就砍掉，效率最高。

有些约束不是单点的，而是依赖前面的选择。比如“第i个人不能和第i-1个人选同一个任务”这种，其实已经被used数组覆盖了，因为同一个任务不能选两次。再比如“相邻两个人不能选相邻编号的任务”，这种约束需要读match[person-1]，检查Math.abs(task - match[person - 1]) != 1。这种检查必须放在当前层，因为只有递归到这一层，前一个人的选择才是确定的。写的时候注意边界：person == 0时没有前一个人，要跳过这个检查，否则会数组越界或者读到-1。

还有一种约束是“整体约束”，比如“选出的任务编号之和必须为偶数”。这种约束没法在单层完全判断，但可以做可行性剪枝：如果当前和已经是奇数，剩余可选任务全是偶数，那再怎么选也无法变成偶数，可以提前返回。这种剪枝需要预处理剩余任务的和的奇偶性，实现起来复杂一些。大多数配对题的单点约束和相邻约束已经够用，整体约束出现频率不高。先把单点约束写对，再考虑复杂约束，不要一上来就追求完美剪枝。

3.4 结果收集的坑：引用传递与深拷贝

结果收集是回溯里第二容易翻车的地方。result.add(match)和result.add(match.clone())看起来只差一个方法调用，结果完全不同。match是数组，Java里数组是引用类型，result.add(match)存的是同一个数组的引用。递归继续跑，match的内容不断被覆盖，最后result里所有元素都指向同一个数组，打印出来全是最后一种方案。这个坑在List<Integer> path上更隐蔽，因为path是ArrayList，result.add(path)存的是列表引用，path.remove之后，之前存进去的也变了。

正确做法是在叶子节点做深拷贝。数组用clone()，列表用new ArrayList<>(path)。如果结果集很大，深拷贝会成为性能瓶颈，因为每个方案都要复制一份。这时候可以考虑用回溯生成字符串或者编码后的整数，减少内存占用；或者不存所有方案，只计数，题目只要方案数时就没必要存。我在模拟项目里遇到过结果集几十万条的情况，存List<int[]>直接把内存打满，后来改成边搜边处理，不保留全量结果，问题就解决了。所以收集结果之前先问一句：真的需要所有方案吗？还是只需要数量、最优解或者前k个？

还有一个细节：如果match初始化为-1，叶子节点克隆出来的数组里可能包含-1吗？不会，因为走到叶子节点时每个位置都被赋值了。但如果在递归中途提前收集，就可能读到-1。所以收集结果的位置一定要在递归出口，不要在中途。有人为了“提前输出部分方案”在递归中间加打印，打出来的路径可能不完整，这不是bug，是位置不对。调试时可以打印，但正式收集必须等路径完整。

3.5 剪枝的三种常见姿势

剪枝是回溯从“能跑”到“跑得快”的关键。配对约束题里常见的剪枝分三类。第一类是可行性剪枝：当前选择直接违反约束，或者剩余选择不可能满足约束，立即返回。比如conflict[person][task]为真，直接跳过；再比如剩余人数少于剩余可选任务数，说明无解，提前返回。第二类是最优性剪枝：题目要求最优解时，如果当前代价已经超过已知最优解，剪掉。配对题多数是枚举所有方案，这类剪枝用得少，但如果有“配对代价最小”的要求就用得上。第三类是对称性剪枝：交换对称对象得到的解等价，只保留一个代表。

可行性剪枝最好写，收益也最直接。比如在选任务之前，先统计当前人可选的任务数量，如果为0，直接返回，不用进循环。这个统计可以提前算，也可以临时遍历。临时遍历是O(n)，但能避免展开一棵注定失败的子树，通常划算。对称性剪枝收益大但容易写错，后面单独讲。最优性剪枝需要维护当前最优值，递归参数里多带一个当前代价，比较后决定是否继续。三种剪枝不要一次全上，先上可行性剪枝，看性能；不够再加对称性；还慢再考虑搜索顺序优化。剪枝加太多，代码可读性下降，调试成本上升，得不偿失。

4. 配对约束的进阶处理：判重、对称性与搜索顺序

4.1 重复元素怎么去重：排序加同层跳过

全排列的去重是经典话题：数组里有重复元素，要求生成不重复的排列。标准做法是先排序，然后在循环里判断i > 0 && nums[i] == nums[i - 1] && !used[i - 1]，满足则跳过。这个条件的含义是：如果当前元素和前一个元素相同，且前一个元素在当前层还没被使用，说明这两个元素在同一层是等价的，选当前元素会产生和选前一个元素重复的分支，所以跳过。!used[i - 1]是关键，它区分了“同一层重复”和“不同层重复”。如果写成used[i - 1]，条件反了，会漏解。

配对题里的“重复”有两种。一种是第一组对象有重复标签，比如两个人都叫“同类型”，他们可选的任务集合完全一样，交换他们得到的方案在业务上可能被视为同一种。这种去重需要在第一组对象层面做，先按可选集合分组，同组内只展开一个代表。另一种是第二组对象有重复，比如两个任务完全等价，交换任务编号得到的方案重复。这种去重和第二组对象的排序有关，但配对问题里任务编号通常有业务含义，不能随便交换，所以去重要谨慎。不要看到“重复”就套全排列去重模板，先确认重复的定义。

我见过一个案例：题目要求“人员分组，每组两人”，人员有重名但工号不同，工号不同就是不同人，不能去重。有人看到名字相同就加了去重，结果漏掉了合法方案。所以去重的前提是“对象在业务上等价”，不是“看起来一样”。如果拿不准，先不去重，用Set对最终结果做去重，虽然慢一点，但不会错。等确认了等价关系，再把去重前移到搜索过程。正确性优先于性能，这个顺序不能反。

4.2 对称性剪枝：固定第一个元素，减少一半搜索

配对问题里最常见的对称性是两组对象角色可互换。比如n个男生和n个女生配对，约束是对称的“某男生不能和某女生配”，那么把所有配对中的男生女生互换，得到的仍然是一个合法方案。这种对称性意味着搜索空间里有一半是重复的。剪枝方法是固定第一个男生必须配第一个女生，或者固定第一个男生配某个特定女生，只搜索这一半。这个剪枝能把方案数直接减半，效果立竿见影。

但固定第一个元素有前提：对称变换必须保持约束不变。如果约束矩阵不对称，比如“男生A不能和女生B配”但“女生B可以和男生A配”这种语义上说不通，实际上矩阵不对称可能代表不同的约束含义，这时候固定就可能漏解。另一个前提是两组对象数量相等且角色确实可互换。如果第一组是“人”，第二组是“任务”，人和任务显然不能互换，就不存在这种对称性。所以用之前先问：交换两组对象，问题还是同一个问题吗？答案是肯定的，才能固定。

固定之后，代码改动很小：在递归的第一层，只允许选特定的那个对象。比如if (person == 0 && task != 0) continue;。但要注意，这只在“完全对称且无其他约束破坏对称性”时成立。如果题目还要求“第一个男生必须配最后一个女生”，那固定条件就要跟着变。对称性剪枝是收益高但风险也高的优化，写完一定要用一个小规模用例对拍，确认剪枝后的结果和剪枝前一致。别嫌麻烦，漏解比超时更难发现。

4.3 搜索顺序的影响：先处理约束最多的元素

搜索顺序对回溯性能影响很大。同样的搜索空间，先展开分支少的那一层，树会窄很多。配对问题里，每个人可选的任务数量不同，有的人只能选两个任务，有的人五个任务都能选。如果按人员编号顺序递归，先处理可选多的人，树会很宽；先处理可选少的人，树会窄。这就是“最少剩余值”启发式，简称MRV。实现上，可以在递归前动态选择当前可选任务最少的那个人，而不是固定按person递增。

具体做法是维护一个未分配人员集合，每层遍历这个集合，找出可选任务数最少的人，把他作为当前决策点。选完之后从集合中移除，递归，回来再放回。这样递归参数不再是person，而是“剩余人员集合”。代码会比固定顺序复杂一些，但剪枝效果明显。尤其是约束密集的题目，有的人可选任务为0，直接返回；有的人可选任务为1，被迫选择，树的分支迅速收窄。固定顺序则可能先展开一个可选五个任务的人，产生五个分支，每个分支再慢慢发现后面有人无解，浪费很多时间。

不过MRV也有代价：每层都要遍历剩余人员并统计可选数，增加了单层开销。如果n很小，这个开销可能超过剪枝收益。我的经验是n≤6时固定顺序就够，n≥7且约束不均匀时再考虑MRV。另外，MRV改变的是搜索顺序，不改变结果集，所以对拍时结果应该完全一致，只是顺序可能不同。如果结果集顺序有要求，比如按字典序输出，MRV会打乱顺序，需要额外排序。这一点在题目有输出顺序要求时要特别注意。

4.4 冲突矩阵与位运算加速

n不大时，used数组和conflict矩阵的访问都是O(1)，已经够快。但如果n到20左右，或者递归调用次数上百万，位运算能把常数降下来。核心思路是用一个整数的二进制位表示“哪些任务已被使用”，usedMask的第j位为1表示任务j被占用。判断任务j是否可用，只需(usedMask & (1 << j)) == 0；标记使用，usedMask | (1 << j)；撤销时不需要额外操作，因为递归参数传的是值，返回后自然恢复。这比修改全局used数组再撤销更简洁，也避免了忘记恢复的风险。

冲突矩阵也可以压缩。如果每行的冲突任务不多，可以把每行的可选任务预先算成一个位掩码availableMask[person]，递归时用usedMask取反再和它按位与，得到当前可选集合。代码片段：

static void dfs(int person, int usedMask) { if (person == n) { count++; return; } int available = ((1 << n) - 1) & ~usedMask & availableMask[person]; while (available != 0) { int taskBit = available & -available; // 取最低位的1 int task = Integer.numberOfTrailingZeros(taskBit); dfs(person + 1, usedMask | taskBit); available ^= taskBit; } }

这段代码用available & -available取最低位的1，用numberOfTrailingZeros得到任务编号，然后异或掉这一位继续循环。好处是不用遍历0到n-1，只遍历可选任务，分支少的时候循环次数大幅减少。位运算的缺点是n超过31时1 << n会溢出，Java的int只有32位，n>30就不能直接用。n在20以内用int足够，n到60用long，再大就不适合位掩码了。配对题一般n不会太大，位运算是值得掌握的加速手段。

5. 完整实操：一道配对约束题的从0到1

5.1 题目定义与输入输出

构造一道模拟题：有n个人和n个任务，每个人必须做一个任务，每个任务只能被一个人做。给定一个n x n的布尔矩阵conflict，conflict[i][j]为true表示第i个人不能做第j个任务。要求输出所有可行的分配方案，每个方案是一个长度为n的数组，第i个元素表示第i个人做的任务编号。如果无解，输出0。这个题目足够典型，涵盖了配对约束的核心：一一对应、冲突过滤、枚举所有方案。输入规模设为n≤8，方便对比循环枚举和回溯的性能。

输入示例：n=4，冲突矩阵里第0个人不能做任务1，第1个人不能做任务0，第2个人不能做任务3，第3个人不能做任务2。输出应该是所有满足条件的排列。这个矩阵是对称的，所以存在交换对称性，但为了演示通用性，我们先不启用对称性剪枝。先写循环枚举版本，再写回溯版本，最后加剪枝对比。所有代码都在本地模拟环境跑过，数据只代表趋势，不代表绝对性能。

5.2 循环枚举版实现

四层循环的版本前面已经写过，这里补上完整的冲突矩阵初始化和结果计数。循环枚举版的核心是“每层选一个任务，排除已选和冲突”。代码结构固定，n=4时四层循环，n=5时五层，n=6时六层。为了对比，我们写一个n=4的版本，统计方案数。实际跑下来，n=4时循环枚举和回溯的差距不大，因为搜索空间只有24种排列，循环枚举的重复判断开销反而更小。但n=6时，循环枚举的六层循环代码已经很长，回溯的递归代码长度不变，可读性优势明显。

循环枚举版还有一个问题是“结果存储”。如果要把所有方案存到List<int[]>，每层循环的叶子节点需要result.add(p.clone())。如果不存，只计数，代码更短。为了和回溯对比，我们统一只计数。循环枚举的计数变量在叶子节点递增。跑n=4、n=5、n=6三组数据，记录方案数和大致耗时。n=6时6!是720，循环枚举的实际迭代次数远大于720，因为每层都从0到5扫，靠continue跳过，实际循环次数是6的6次方级别。这个差距在n=6时已经能感觉到，n=7、n=8会急剧放大。

5.3 回溯版实现（基础加剪枝）

回溯版先写基础骨架，再加可行性剪枝。基础版就是前面的backtrack(person)，每层遍历任务，跳过已用和冲突。加可行性剪枝：在进入循环之前，先统计当前人可选的任务数量，如果为0，直接返回。统计可以放在循环里做，也可以提前算。更进一步的剪枝是“如果剩余可选任务数少于剩余人数，返回”，但这个判断需要全局统计，实现复杂，先不加。对称性剪枝也先不加，保证结果正确。

完整代码：

import java.util.ArrayList; import java.util.List; public class PairDemo { static int n = 6; static boolean[][] conflict = new boolean[n][n]; static boolean[] used = new boolean[n]; static int[] match = new int[n]; static int count = 0; static List<int[]> result = new ArrayList<>(); public static void main(String[] args) { // 模拟冲突：第i个人不能做第i个任务，制造一些限制 for (int i = 0; i < n; i++) { conflict[i][i] = true; } long start = System.nanoTime(); backtrack(0); long end = System.nanoTime(); System.out.println("方案数：" + count); System.out.println("耗时(ms)：" + (end - start) / 1_000_000.0); } static void backtrack(int person) { if (person == n) { count++; result.add(match.clone()); return; } for (int task = 0; task < n; task++) { if (used[task]) continue; if (conflict[person][task]) continue; used[task] = true; match[person] = task; backtrack(person + 1); used[task] = false; match[person] = -1; } } }

这段代码在n=6、对角线冲突的情况下能跑出结果。对角线冲突意味着每个人不能做自己的编号任务，这是一个典型的错排问题，方案数是!6 = 265。回溯会搜索所有排列并过滤，实际递归调用次数略大于720。如果加可行性剪枝，在每层开始前检查当前人是否有可选任务，能提前砍掉一些分支。但在这个例子里，每个人至少还有n-1个可选任务，剪枝收益不明显。换一个约束更密集的矩阵，比如每个人只能做两个任务，剪枝收益就会显现。

5.4 测试与性能对比

为了看趋势，我们跑三组规模：n=5、n=6、n=7，冲突矩阵设为“每个人不能做自己的编号任务”，即错排。记录循环枚举版和回溯版的方案数与大致耗时。循环枚举版在n=7时需要七层循环，代码太长，这里用递归模拟循环枚举的“每层全扫”行为作为对照，实际手写七层循环不现实。下表是模拟环境下的趋势数据，耗时单位毫秒，只用于说明量级差异：

从表里能看出，n增大时差距拉大。n=8时回溯基础版比循环枚举风格快一个数量级，加剪枝后又快一些。这个数据不是绝对基准，因为循环枚举风格是用递归模拟的，真实手写循环在n=5、6时可能更快，但n=8时手写八层循环已经不现实。结论是：小规模下两者差距不大，规模上来后回溯的结构优势明显。方案数本身增长很快，n=8的错排已经一万多，如果题目要求存所有方案，内存会成为新瓶颈，这时候要考虑是否真的需要全量存储。

5.5 结果验证：用暴力小规模对拍

写完回溯版，一定要对拍。方法很简单：写一个独立的暴力版本，用最笨的办法生成所有排列，逐个检查约束，统计方案数。n≤6时暴力版本跑得动。把两个版本的方案数对比，如果一致，说明回溯的剪枝没有漏解；再把方案集合排序后对比，如果完全一致，说明结果收集也没有问题。对拍是发现“剪枝写错”和“恢复现场遗漏”最有效的手段，比盯着代码看半天强。

对拍时注意两点：一是两个版本使用同一份冲突矩阵，不要一个初始化了、另一个没初始化；二是结果比较时注意顺序，如果回溯改变了搜索顺序，方案集合的顺序可能不同，排序后再比。我一般写一个check方法，把List<int[]>转成List<String>，每个数组拼成逗号分隔的字符串，排序后比较。这样能避免数组引用比较的坑。对拍通过之后，再逐步加剪枝，每加一个剪枝就对拍一次，确保正确性不被优化破坏。这个习惯能省掉大量调试时间。

6. 常见问题与排查技巧实录

6.1 常见问题速查表

回溯和配对约束题的错误有很强的规律性，下面这张表覆盖了大多数情况：

这张表不是让你背，是让你在遇到问题时快速定位。实际排查时，先看方案数，再看结果内容，最后看性能。方案数不对，优先查正确性；方案数对但慢，优先查剪枝；方案数对但内存爆，优先查结果收集。顺序对了，排查效率会高很多。

6.2 调试回溯代码的三个土办法

第一个办法是打印递归树。在递归入口打印当前层号和路径，在递归出口打印完整方案，在返回前打印“撤销”信息。输出会很多，但能直观看到每一层选了什么、什么时候回溯、撤销有没有执行。n=3时打印量还能接受，n=5以上建议只打印前几十行，或者加条件只打印特定分支。打印的时候用缩进表示层级，看起来更清楚。

第二个办法是缩小规模。把n从6改成3，手算所有方案，和程序输出对比。n=3时全排列只有6种，约束也容易手算。如果n=3都对，n=6错，大概率是规模变大后的边界问题，比如数组越界、结果集扩容、剪枝条件在深层失效。如果n=3就错，那是骨架问题，先别急着看剪枝，把used和恢复现场检查一遍。缩小规模是最快的定位手段，比读代码快。

第三个办法是单步调试。在IDE里给递归入口和出口打断点，观察used数组和match数组的变化。重点看递归返回后，used是否恢复、match是否被覆盖。单步调试适合逻辑复杂、打印也看不清的情况。缺点是慢，n=6时递归调用几百次，单步会崩溃。通常结合前两个办法，先缩小规模，再单步关键分支。

6.3 性能突然变差的排查顺序

性能问题不要一上来就改算法，先按顺序排查。第一，看递归调用次数。加一个计数器，在递归入口递增，跑完打印。如果调用次数远大于方案数乘以n，说明无效分支太多，剪枝不足。第二，看剪枝是否生效。把剪枝条件临时改成if (false)，对比调用次数。如果关掉剪枝后次数暴增，说明剪枝有用；如果关掉后次数差不多，说明剪枝条件根本没命中，可能写错了位置或者条件太宽松。第三，看结果收集。如果result.add(match.clone())在叶子节点执行了几十万次，内存和GC会成为瓶颈，考虑只计数不存储。

第四，看搜索顺序。把人员顺序打乱，或者按可选任务数排序，看调用次数是否变化。如果变化很大，说明搜索顺序是主要矛盾，考虑上MRV。第五，看数据结构。used数组和conflict矩阵的访问是O(1)，一般不是瓶颈；如果用了List.contains判断是否用过，那就是O(n)，换成boolean[]能立刻提速。排查顺序从宏观到微观，先确认算法层面的搜索空间，再看实现层面的常数开销，别反过来。

6.4 我踩过的几个坑

第一个坑是恢复现场只恢复了一半。used[task] = false写了，match[person] = -1忘了写。大部分时候不影响结果，因为下一次赋值会覆盖，但在某些剪枝逻辑里会读到脏值，导致莫名其妙地漏解。后来我养成了习惯：递归前后的修改成对出现，中间不插其他逻辑，写完立刻检查。第二个坑是剪枝条件写反。比如“如果当前人可选任务为0就返回”，写成了“如果不为0就返回”，结果第一个分支就返回，方案数为0。这种错误编译器不报，只能靠小规模对拍发现。

第三个坑是对称性剪枝用在不该用的地方。有一次题目里两组对象角色不同，我固定了第一个配对，结果漏掉了所有第一个对象不配第一个对象的解。后来我定了规矩：用对称性剪枝之前，先写注释说明“为什么对称”，写不出来就不用。第四个坑是结果集内存溢出。题目要求输出所有方案，我存了List<int[]>，n=10时方案数几百万，直接OOM。后来改成边搜边写文件，或者只返回前1000个，问题解决。这些坑都不高深，但每一个都花了不少时间调试，记下来比事后忘掉强。

最后再分享一个小技巧：把冲突矩阵提前转成“每个人可选任务列表”，递归时直接遍历这个列表，而不是遍历0到n-1再判断冲突。这样循环次数只和可选任务数有关，约束越密集收益越大。代码上就是预处理一个List<Integer>[] choices，递归里for (int task : choices[person])。我在几个模拟项目里都这么干，尤其是约束密集的时候，提前算好可选列表比在循环里反复查矩阵更顺手，代码也更好读。