回溯例题：全排列

看一下灵神的代码
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
path = [0] * n
ans = []

    # 枚举 path[i] 填 remain（剩余数字）中的哪个数
    def dfs(i: int, remain: Set[int]) -> None:
        if i == n:
            ans.append(path.copy())
            return

        for x in remain:
            path[i] = x
            dfs(i + 1, remain - {x})

    dfs(0, set(nums))
    return ans

用bool判断用过没用过就是下面这种
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
path = [0] * n # 所有排列的长度都是一样的 n
on_path = [False] * n
ans = []

    # 枚举 path[i] 填 nums 的哪个数
    def dfs(i: int) -> None:
        if i == n:
            ans.append(path.copy())  # 也可以写 path[:]
            return
        for j, on in enumerate(on_path):
            if not on:
                path[i] = nums[j]  # 从没有选的数字中选一个
                on_path[j] = True  # 已选上
                dfs(i + 1)
                on_path[j] = False  # 恢复现场
                # 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行

    dfs(0)
    return ans

复杂度分析
时间复杂度：O(n⋅n!)，其中 n 为 nums 的长度。视频中提到，搜索树中的节点个数低于 3⋅n!。实际上，精确值为 ⌊e⋅n!⌋，其中 e=2.718⋯ 为自然常数。有 O(n!) 个叶节点，每个叶节点花费 O(n) 的时间复制 path 数组，因此时间复杂度为 O(n⋅n!)。
空间复杂度：O(n)。返回值的空间不计入。

排列型回溯：46 全排列

1. 前提条件

全排列问的是：

给 nums 里的所有数，重新排列出所有顺序。

例如：

nums = [1,2,3]

答案：

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

核心和组合不同：

组合：不能回头选，靠 start
排列：每一层都可以从头选，靠 used[]

2. 核心概念

排列型每一层是在问：

当前位置放谁？

比如 [1,2,3]：

第 0 个位置：可以放 1/2/3
第 1 个位置：放剩下没用过的
第 2 个位置：放最后一个

所以需要：int used[MAXN];

表示：

这个数有没有被当前 path 用过

3. 固定模板
   void dfs()
   {
   if(pathSize == numsSize)
   {
   保存 path;
   return;
   }

   for(int i = 0; i < numsSize; i++)
   {
   if(used[i])
   {
   continue;
   }

    used[i] = 1;
    path[pathSize++] = nums[i];
   
    dfs();
   
    pathSize--;
    used[i] = 0;
   

   }
   }

核心还是：

选择
递归
撤销

只不过排列型撤销两个东西：

pathSize--
used[i] = 0

4. 为什么不用 start？

组合型：

[1,2] 和 [2,1] 算同一个

所以用：

dfs(i + 1);

防止回头。

排列型：

[1,2] 和 [2,1] 是两个不同答案

所以每一层都要：

for(int i = 0; i < numsSize; i++)

从头扫一遍。

但是不能重复用同一个数，所以用：used[i]或者用bool判断你是否选择过

int** permute(int* nums, int n, int* returnSize, int** returnColumnSizes) {
// 计算 n!
int ansSize = 1;
for (int i = 2; i <= n; i++) {
ansSize *= i;
}

int** ans = malloc(ansSize * sizeof(int*));
*returnColumnSizes = malloc(ansSize * sizeof(int));
*returnSize = 0;

int* path = malloc(n * sizeof(int));
bool* on_path = calloc(n, sizeof(bool)); // 所有排列的长度都是一样的 n

// 枚举 path[i] 填什么数字
void dfs(int i) {
    if (i == n) {
        ans[*returnSize] = malloc(n * sizeof(int));
        memcpy(ans[*returnSize], path, n * sizeof(int));
        (*returnColumnSizes)[*returnSize] = n;
        (*returnSize)++;
        return;
    }

    for (int j = 0; j < n; j++) {
        if (!on_path[j]) {
            path[i] = nums[j]; // 从没有选的数字中选一个
            on_path[j] = true; // 已选上
            dfs(i + 1);
            on_path[j] = false; // 恢复现场
            // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
        }
    }
}

dfs(0);

free(path);
free(on_path);
return ans;

}

它分成 4 块：

1. 先算一共有多少个答案
2. 给答案数组 ans 分配空间
3. 准备 path 和 on_path
4. dfs 填排列
5. 计算一共有多少个排列

int ansSize = 1;
for (int i = 2; i <= n; i++) {
ansSize *= i;
}

如果 n = 3：

ansSize = 1 × 2 × 3 = 6

因为 [1,2,3] 一共有：

3! = 6

个排列。

2. 给答案分配空间

int** ans = malloc(ansSize * sizeof(int*));

ans 是二维数组。

可以理解成：

ans[0] -> 一个排列
ans[1] -> 一个排列
ans[2] -> 一个排列
...

比如：

ans[0] = [1,2,3]
ans[1] = [1,3,2]
ans[2] = [2,1,3]

所以 ans 本身是：int**

*returnColumnSizes = malloc(ansSize * sizeof(int));

这个是 LeetCode 要求的。

它记录每一行有几个元素。

因为全排列每一行长度都是 n，比如：

[1,2,3] 长度 3
[1,3,2] 长度 3
[2,1,3] 长度 3

所以后面每一行都填 n。

*returnSize = 0;

表示：目前已经保存了 0 个排列

以后每找到一个排列，就：

(*returnSize)++;

3. 准备 path 和 on_path
   int* path = malloc(n * sizeof(int));

path 是当前正在填的排列。

比如搜索过程中：

path = [1, _, _]
path = [1, 2, _]
path = [1, 2, 3]
bool* on_path = calloc(n, sizeof(bool));

on_path[j] 表示：

nums[j] 这个数有没有被用过

如果：

nums = [1,2,3]

一开始：

on_path = [false, false, false]

选了 1 之后：

on_path = [true, false, false]

表示 nums[0] = 1 已经用过了。

4. dfs 的含义
   void dfs(int i)

这里的 i 表示：

现在正在填 path[i]

比如：

dfs(0)：填 path[0]
dfs(1)：填 path[1]
dfs(2)：填 path[2]
dfs(3)：说明 path[0], path[1], path[2] 都填完了

5. 结束条件
   if (i == n) {

如果 n = 3，当 i == 3 时，说明：

path[0], path[1], path[2]

都已经填好了。

比如：

path = [1,2,3]

这就是一个完整排列。

保存答案：

ans[*returnSize] = malloc(n * sizeof(int));

给当前这一行分配空间。

比如：

ans[0] 准备存 [1,2,3]
memcpy(ans[*returnSize], path, n * sizeof(int));

把 path 复制到 ans[*returnSize]。

memcpy 理解成：

把 path 里的 n 个 int 复制到 ans 当前这一行

等价于手写：

for(int k = 0; k < n; k++) {
ans[*returnSize][k] = path[k];
}
(*returnColumnSizes)[*returnSize] = n;

告诉 LeetCode：

这一行有 n 个数
(*returnSize)++;

表示：

答案数量 +1

6. for 循环：当前位置填谁
   for (int j = 0; j < n; j++) {

意思是：

我现在要填 path[i]
尝试用 nums[0], nums[1], nums[2]...
if (!on_path[j]) {

如果 nums[j] 没用过，就可以选。

path[i] = nums[j];

把这个数填到当前位置。

比如：

i = 0, j = 0
path[0] = nums[0] = 1

得到：

path = [1, _, _]
on_path[j] = true;

标记：

nums[j] 已经用过
dfs(i + 1);

去填下一个位置。

如果现在填完 path[0]，下一步就填：

path[1]
on_path[j] = false;

恢复现场。

意思是：

刚刚试过 nums[j] 了
现在退回来
让 nums[j] 可以给别的排列继续使用
用 [1,2,3] 看一次

开始：

dfs(0)
path = [,,_]
on_path = [F,F,F]

选 1：

path = [1,,]
on_path = [T,F,F]
dfs(1)

选 2：

path = [1,2,_]
on_path = [T,T,F]
dfs(2)

选 3：

path = [1,2,3]
on_path = [T,T,T]
dfs(3)

i == n，保存：

[1,2,3]

然后回溯，撤销 3：

on_path = [T,T,F]

再回去撤销 2，尝试选 3：

path = [1,3,_]
on_path = [T,F,T]

再选 2：

path = [1,3,2]

保存。

最核心三句

path[i] = nums[j];
on_path[j] = true;
dfs(i + 1);
on_path[j] = false;

意思就是：

把 nums[j] 填到第 i 个位置
标记它已经用过
递归去填下一个位置
回来后撤销标记，换别的数试

path 不用恢复，因为下一次会直接覆盖 path[i]。

6. 易错点

7. 排列型不能用 start，否则会漏掉 [2,1] 这种顺序。

8. 每一层都从 i=0 开始枚举。

9. 必须 used[i] 防止重复使用同一个数。

10. 回溯时既要 pathSize--，也要 used[i]=0。

11. 保存答案时要复制 path，不能直接保存 path 指针。

排列型回溯 = 每个位置枚举一个没用过的数。