如何理解LeetCode全排列题中的这段Java回溯递归代码？

核心设计思路 #

这个解法的核心是按位固定排列元素：用参数first表示当前正在确定排列的第first位下标，所有下标小于first的位置已经固定好元素，只需要从下标>=first的剩余元素里选一个放到first位，再递归处理后面的位置即可。

两次swap的作用 #

代码里的两次交换是回溯算法的典型“操作-撤销”逻辑：

• 第一次Collections.swap(output, first, i)：把选中的第i位元素交换到当前要固定的first位，相当于确定了第first位的取值
• 递归调用backtrack(n, output, res, first + 1)：first位已经固定，递归处理下一位的排列
• 第二次Collections.swap(output, first, i)：撤销之前的交换操作，把数组还原到交换前的状态，保证下一轮循环选其他元素时，数组是初始的正确状态（因为List是引用类型，所有递归操作共享同一个集合，必须撤销修改避免影响后续逻辑）

i == first时交换的意义 #

当循环第一次执行i = first时，交换两个相同下标的元素看起来没有实际修改，但是这么写是为了统一逻辑，省略额外分支判断：

• 这个场景对应的是“第first位就选原来位置的元素”的情况，属于排列的合法情况之一
• 即使不写判断跳过交换，Collections.swap底层也会自动处理相同下标的情况，不会有额外性能开销，反而少写了分支代码，逻辑更简洁不容易出错

实际执行流程示例 #

以输入[1,2,3]为例，完整执行流程如下：

1. 初始调用backtrack，first=0，数组为[1,2,3]
   • 循环i=0：
     • 交换0和0，数组不变，进入first=1的递归
     • first=1时循环i=1：
       • 交换1和1，数组不变，进入first=2的递归
       • first=2时循环i=2：
         • 交换2和2，数组不变，进入first=3的递归，满足first == n=3，将[1,2,3]加入结果集
         • 撤销交换2和2，返回上一层
       • 循环i=2：
         • 交换1和2，数组变为[1,3,2]，进入first=2的递归
         • first=2交换2和2，进入first=3，将[1,3,2]加入结果集
         • 撤销交换2和2，再撤销交换1和2，数组还原为[1,2,3]，返回上一层
     • 撤销交换0和0，数组不变
   • 循环i=1：
     • 交换0和1，数组变为[2,1,3]，进入first=1的递归
     • 后续逻辑会生成[2,1,3]、[2,3,1]两个结果，最后撤销交换还原数组为[1,2,3]
   • 循环i=2：
     • 交换0和2，数组变为[3,2,1]，进入first=1的递归
     • 后续逻辑会生成[3,2,1]、[3,1,2]两个结果，最后撤销交换还原数组为[1,2,3]
2. 所有递归执行完毕，结果集里就包含了全部6种排列。

内容的提问来源于stack exchange，提问作者zzzbei