11、递归与回溯：全排列问题
全排列问题，是理解回溯算法最好的入门题。我个人觉得，它把递归的「深度优先」和回溯的「状态撤销」这两个核心概念，展现得淋漓尽致。
说白了，就是给你几个不同的数字，比如 [1,2,3]，让你列出所有可能的排列方式。3 个数字有 6 种排列，4 个数字有 24 种，n 个数字就是 n! 种。嗯，这个增长很快，但递归处理起来却很优雅。
问题定义
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
递归思路：选数填空
我是这么理解全排列的：想象有 n 个空位，我们要依次把数字填进去。
- 第一个空位，可以从 n 个数字中任选一个
- 第二个空位，从剩下的 n-1 个数字中选一个
- ……
- 最后一个空位，只剩一个数字，没得选
你想想看，这不就是一棵多叉树吗？每一层对应一个空位，每个节点代表「当前已选数字的序列」。叶子节点就是完整的排列。
核心思想：递归函数负责「在当前空位，尝试所有还没用过的数字」。每选一个，就递归到下一层。当所有空位填满，就得到一个排列。
回溯的「撤销」操作
这里有个关键点：当你递归返回时，必须把刚才选的那个数字「还回去」。为什么？
举个例子。你选了 1 放在第一个位置，然后递归处理剩下的 [2,3]。等递归返回，你得到了所有以 1 开头的排列。这时候，如果你不把 1 从「已选列表」中移除，下一个循环尝试把 2 放在第一个位置时，1 还在已选列表里，你就没法选 1 了——这显然不对。
所以，回溯的「撤销」操作，本质上就是：在递归调用之后，把状态恢复成调用之前的样子。
我的习惯：写回溯代码时，先写「选择」和「递归」，再写「撤销」。这三行代码通常紧挨着，形成一个固定模式。你写多了就会发现，回溯题的代码结构都差不多。
代码实现
来看 C 语言实现。我建议你重点关注 backtrack 函数中的那三行核心代码。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 交换两个整数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 回溯函数
// nums: 原始数组
// numsSize: 数组长度
// start: 当前要确定的位置
// result: 存储所有排列
// returnSize: 当前已找到的排列数量
void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize) {
// 递归终止条件：所有位置都已确定
if (start == numsSize) {
// 保存当前排列
result[*returnSize] = (int*)malloc(numsSize * sizeof(int));
memcpy(result[*returnSize], nums, numsSize * sizeof(int));
(*returnSize)++;
return;
}
// 尝试将每个未使用的数字放到 start 位置
for (int i = start; i < numsSize; i++) {
// 选择：将 nums[i] 放到 start 位置
swap(&nums[start], &nums[i]);
// 递归：处理下一个位置
backtrack(nums, numsSize, start + 1, result, returnSize);
// 撤销：恢复原状
swap(&nums[start], &nums[i]);
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
// 计算排列总数：n!
int total = 1;
for (int i = 1; i <= numsSize; i++) {
total *= i;
}
// 分配结果数组
int** result = (int**)malloc(total * sizeof(int*));
*returnSize = 0;
// 开始回溯
backtrack(nums, numsSize, 0, result, returnSize);
// 设置每行的列数
*returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
for (int i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = numsSize;
}
return result;
}
核心逻辑流程图
下面这张图展示了以 [1,2,3] 为例，回溯算法是如何一步步生成所有排列的。注意看「选择」和「撤销」的交替过程。
代码执行过程详解
我们拿 [1,2,3] 走一遍，看看递归和回溯是怎么配合的。
| 递归深度 | 当前数组状态 | 操作 | 说明 |
|---|---|---|---|
| 0 | [1,2,3] | start=0, i=0, 交换(0,0) | 选 1 到位置 0 |
| 1 | [1,2,3] | start=1, i=1, 交换(1,1) | 选 2 到位置 1 |
| 2 | [1,2,3] | start=2, i=2, 交换(2,2) | 选 3 到位置 2，得到 [1,2,3] |
| 2 | [1,2,3] | 撤销交换(2,2) | 恢复原状 |
| 1 | [1,2,3] | i=2, 交换(1,2) | 选 3 到位置 1 |
| 2 | [1,3,2] | start=2, i=2, 交换(2,2) | 选 2 到位置 2，得到 [1,3,2] |
| 2 | [1,3,2] | 撤销交换(2,2) | 恢复原状 |
| 1 | [1,3,2] | 撤销交换(1,2) | 恢复成 [1,2,3] |
| 0 | [1,2,3] | i=1, 交换(0,1) | 选 2 到位置 0 |
| …… | …… | …… | 继续类似过程 |
我曾经踩过的坑：刚开始写回溯时，我经常忘记在递归调用后面写撤销操作。结果就是，第一次递归返回后，数组状态已经变了，后面的循环全乱套了。调试了整整一下午才找到原因。所以我的建议是：写回溯代码时，先把「选择」「递归」「撤销」这三行写在一起，形成一个不可分割的单元。
时间复杂度分析
全排列的时间复杂度是 O(n!)，这个没法优化，因为 n! 个排列必须全部生成。空间复杂度方面，递归调用栈的深度是 n，所以是 O(n)。
不过在实际工程中，n 通常不会太大。n=10 时，10! = 3628800，已经接近千万级别了。如果 n 再大，就要考虑剪枝或者用迭代法了。
回溯算法的通用模板
从全排列问题中，我们可以提炼出回溯算法的通用模板。你以后遇到任何回溯题，都可以套这个框架。
void backtrack(参数列表) {
if (满足终止条件) {
保存结果;
return;
}
for (选择 in 所有可选列表) {
做选择;
backtrack(更新后的参数);
撤销选择;
}
}
我的经验：这个模板看似简单，但真正用好它，关键在于两点：一是搞清楚「可选列表」是什么，二是想明白「撤销」要撤销什么。全排列中，可选列表是「当前未使用的数字」，撤销是「交换回去」。不同题目，这两点的实现方式不同，但思路是一样的。
小结
全排列问题，是理解回溯算法的绝佳入口。它把递归的深度优先遍历和回溯的状态撤销，展现得清清楚楚。
你想想看，整个算法就像一个人在迷宫里探索：每到一个岔路口，选一条路走到底；走不通或者走完了，就退回到上一个路口，换一条路继续走。这个「退回」的动作，就是回溯中的「撤销」。
掌握了全排列，你就掌握了回溯算法的核心思想。后面遇到八皇后、组合总和、子集等问题，你会发现，它们本质上都是同一个套路——只是「选择」和「撤销」的具体形式不同罢了。