回溯算法（有组织的暴力枚举）
很多人一听到“回溯”就头大，觉得这东西太玄乎，跟动态规划一样，听着就不好惹。其实在我看来，回溯算法的本质，就是一种“有组织的暴力枚举”。它没有那么神秘，你甚至可以把它理解成深度优先搜索（DFS）的一种特殊应用。
想象一下你在走一个迷宫，有很多条岔路。你怎么走？很简单，随便选一条路走到底，如果发现是死胡同，或者不是出口，怎么办？退回来，回到上一个岔路口，换一条没走过的路继续走。把这个过程重复下去，直到找到出口或者所有路都试过。
看，这就是回溯。“回”就是退回一步，“溯”就是寻找另一条路。
回溯算法，说白了就三样东西：
路径（Path）：你已经做出的选择，构成了当前的路径。
选择列表（Choices）：在当前路径下，你还能做哪些选择。
结束条件（End Condition）：你什么时候知道该停了，要么是找到一个解，要么是这条路走不通了。
掌握了这个框架，所有回溯问题都是一个套路。今天我们就拿一个最经典的问题——全排列（LeetCode 46. Permutations）——来把回溯这个东西彻底盘明白。
问题：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
比如，输入 [1, 2, 3]，你应该返回： [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
解法一：最标准、最通用的回溯思路
这是我最推荐初学者掌握的，也是最能体现回溯思想的方法。咱们就按照上面说的三要素来套。
思考过程： 我要生成 [1, 2, 3] 的全排列。
路径：就是一个列表，比如
[1]，[1, 2]，[1, 2, 3]。选择列表：在当前路径下，我还能选哪些数？比如路径是
[1]，那么我还能选2和3。结束条件：当路径的长度等于原数组的长度时，说明一个完整的排列已经生成了，把它加到结果集里。
怎么知道哪些数还能选？最简单粗暴的办法，就是搞一个 boolean 数组 used，和原数组一样长。used[i] = true 就表示 nums[i] 这个数已经被用过了。
好了，递归函数的样子就出来了。我管它叫 backtrack。
backtrack(结果集, 当前路径, 原数组, used数组)
递归逻辑：
检查结束条件：如果
当前路径.size() == 原数组.length，说明找到了一个解，把它拷贝一份放进结果集，然后返回。遍历选择列表：从头到尾遍历原数组
nums。做出选择：如果
nums[i]这个数还没被用过（used[i] == false），这就是一个可行的选择。把它加到
当前路径里。把
used[i]标记为true。进入下一层决策：调用
backtrack，让下一层去做选择。
撤销选择（回溯）：当下一层的递归调用结束后，无论它成功与否，我们都要回到当前状态。为了不影响同级的其他选择，必须“恢复现场”。
把刚才加进去的数从
当前路径中移除。把
used[i]重新标记为false。
这个“做出选择 -> 递归 -> 撤销选择”的三部曲，就是回溯算法的灵魂。
import java.util.ArrayList;
import java.util.List;
class Solution1 {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
// 路径
List<Integer> path = new ArrayList<>();
// used数组，记录哪些数字被使用过
boolean[] used = new boolean[nums.length];
backtrack(nums, path, used, result);
return result;
}
private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
// 结束条件：路径长度等于数组长度
if (path.size() == nums.length) {
// 注意：这里必须 new 一个新的 List，因为 path 在后续的回溯中会改变
result.add(new ArrayList<>(path));
return;
}
// 遍历所有可能的选择
for (int i = 0; i < nums.length; i++) {
// 如果这个数字已经被用过了，跳过
if (used[i]) {
continue;
}
// --- 做出选择 ---
path.add(nums[i]);
used[i] = true;
// --- 进入下一层决策 ---
backtrack(nums, path, used, result);
// --- 撤销选择（回溯）---
used[i] = false;
path.remove(path.size() - 1);
}
}
}
分析：这个解法非常直观，逻辑清晰。缺点是需要一个额外的 used 数组来记录状态，空间复杂度是 O(N)。但作为理解回溯的入门，它是最完美的。
解法二：空间优化，原地交换法
用过 used 数组后，我就会想，能不能省掉这个O(N)的空间？回溯的过程，其实是在构建一棵决策树。有没有办法在原数组上直接修改，来反映当前的状态呢？
答案是肯定的，就是交换。
思考过程： 我们可以把排列的过程看成是“填位置”。
第 0 个位置，可以填
nums里的任意一个数。怎么实现？把选中的数和nums[0]交换。第 1 个位置，可以填剩下
n-1个数里的任意一个。怎么实现？把选中的数和nums[1]交换。以此类推……
这样，我们的递归函数需要一个参数 index，表示当前正在决定第 index 个位置该放哪个数。
backtrack(原数组, 当前处理的位置index, 结果集)
递归逻辑：
结束条件：如果
index == nums.length，说明 0 到n-1的位置都填好了，整个数组当前的状态就是一个排列。把它加到结果集。遍历选择列表：第
index位置的选择范围是nums[index]到nums[n-1]之间的所有数。所以我们遍历i从index到n-1。做出选择：将
nums[i]和nums[index]交换。这样就把nums[i]这个数“固定”在了第index位上。进入下一层决策：调用
backtrack(nums, index + 1, result)，去决定第index + 1个位置该放谁。撤销选择（回溯）：为了不影响上层循环的下一次选择，必须把刚才的交换操作还原。再把
nums[i]和nums[index]交换回来。
这个“交换 -> 递归 -> 换回来”的模式，同样是回溯的体现，但它巧妙地用数组自身的状态代替了 used 数组。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
class Solution2 {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
backtrack(nums, 0, result);
return result;
}
private void backtrack(int[] nums, int index, List<List<Integer>> result) {
// 结束条件：当 index 到达数组末尾，说明找到了一个完整的排列
if (index == nums.length) {
// 将 int[] 转换为 List<Integer> 并添加到结果中
List<Integer> permutation = Arrays.stream(nums).boxed().collect(Collectors.toList());
result.add(permutation);
return;
}
// 选择列表：从 index 到末尾的所有元素都可以放到当前 index 位置
for (int i = index; i < nums.length; i++) {
// --- 做出选择：将 i 位置的元素交换到 index 位置 ---
swap(nums, index, i);
// --- 进入下一层决策：处理下一个位置 ---
backtrack(nums, index + 1, result);
// --- 撤销选择（回溯）：将数组恢复原样，以便下一次循环 ---
swap(nums, index, i);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
分析：这个方法省去了 used 数组的空间，空间复杂度降到了 O(1)（如果不算递归栈和结果集的话）。代码更简洁，是回溯问题中一个非常常见的优化技巧。
解法三：跳出递归，迭代实现的“下一个排列”
前面两种都是递归，递归的本质是系统帮我们维护了一个栈。那我们能不能完全不用递归，自己用迭代的方式来实现呢？
这个思路就和回溯不太一样了，但它能解决同样的问题，而且效率可能更高。这是一种基于数学规律的解法，叫做“字典序法”或“下一个排列”（Next Permutation）。
思考过程： 所有排列按字典序排好，比如 [1, 2, 3] 的排列： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1
如果我们能找到一种算法，给定任意一个排列，都能找出它在字典序中的下一个排列，那问题就解决了。
先把数组排序，得到最小的排列（如
[1, 2, 3]）。把它加入结果集。
循环调用“下一个排列”算法，把得到的新排列加入结果集，直到找不到下一个排列（说明已经到了最大的那个，如
[3, 2, 1]）。
“下一个排列”算法： 这个算法有点绕，但很经典。
从后往前找，找到第一个
nums[i] < nums[i+1]的位置i。这个i很关键，它右边的部分[i+1, n-1]是一个降序序列。我们需要在右边找一个比nums[i]大的“最小”数来替换它，这样才能得到一个刚好比当前大的新排列。再从后往前找，找到第一个
nums[j] > nums[i]的位置j。交换
nums[i]和nums[j]。交换后，
[i+1, n-1]这部分仍然是降序的。为了得到字典序最小的下一个排列，需要将这部分翻转，变成升序。
如果第一步找不到 i，说明整个数组是降序的，已经是最大的排列了，不存在下一个。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution3 {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
// 1. 先排序，得到字典序最小的排列
Arrays.sort(nums);
do {
// 2. 将当前排列加入结果集
result.add(toList(nums));
} while (nextPermutation(nums)); // 3. 循环找下一个排列
return result;
}
private boolean nextPermutation(int[] nums) {
// 1. 从后往前找第一个升序对 (i, i+1)
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// 如果 i < 0，说明整个数组是降序，没有下一个排列了
if (i < 0) {
return false;
}
// 2. 从后往前找第一个比 nums[i] 大的数 nums[j]
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
// 3. 交换 i 和 j
swap(nums, i, j);
// 4. 翻转 i 后面的部分
reverse(nums, i + 1);
return true;
}
private List<Integer> toList(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) {
list.add(num);
}
return list;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start) {
int left = start;
int right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
分析：这种方法完全脱离了递归和回溯的思维框架，变成了一个纯粹的数组操作问题。它的逻辑相对固定，但性能通常很好，因为没有递归带来的函数调用开销。在某些场景下，比如面试官追问“能不能不用递归”，这就是一个绝佳的答案。
总结一下
今天我们用三种完全不同的思路把“全排列”这个问题给办了：
标准回溯：使用
used数组，最通用，最能体现回溯的“做选择-撤销选择”模型，是必须掌握的基本功。交换法回溯：在原数组上通过交换来管理状态，是空间优化的经典技巧，展现了对状态压缩的理解。
下一个排列迭代法：基于数学规律的迭代解法，思路清奇，性能优秀，是拓宽解题思路的利器。
从暴力递归，到空间优化，再到完全不同的迭代思路，这就是一个思维提升的过程。回溯的本质就是画一棵决策树，并用代码遍历这棵树。只要你能把这棵树的样子在脑海里画出来，想清楚每个节点需要做什么选择，以及递归返回后如何恢复现场，那回溯问题就没什么好怕的了。