跳转至
纸质书已发行，详情请见这里

# 13.6 练习

## 13.6.1 知识巩固

### 1. 这段排列算法会漏掉结果吗

一个回溯算法按 `1、2、3` 的顺序尝试生成全部排列。每次选择数字 `x` 时，它会：

1. 把 `x` 加到当前路径末尾；
2. 把 `x` 标记为“已使用”；
3. 递归填写下一个位置。

递归返回后，同学只从路径末尾删除了 `x`，然后继续尝试下一个数字。

1. 算法首先得到哪个排列？它还能得到全部 6 个排列吗？
2. 递归返回上一层前，只删除路径末尾的数字是否足够？如果不够，还需要做什么？说明理由。

参考答案

1. 它首先得到 `[1, 2, 3]`，但无法得到全部排列。虽然返回时路径变短了， 数字 1、2、3 的标记仍都是“已使用”，后续分支便没有可选数字。

2. 不够。删除路径末尾的 `x` 后，还必须把 `x` 重新标记为“未使用”。 当前路径和已使用标记共同描述搜索状态；选择时修改了两处，回退时也必须把两处都恢复， 其他分支才能再次选择 `x`。

### 2. 数字的选择顺序重要吗

给定排好序的数组 `[2, 3, 5]` 和目标值 5，每个数可以重复选择。 算法规定每条搜索路径中的数字只能按从小到大的顺序出现。

1. 能得到哪些不同的组合？
2. 为什么同一组数字不需要按不同顺序重复搜索？“从小到大”的限制起到了什么作用？
3. 当前路径为 `[3]`、还差 2 时，下一个候选数是 3。为什么此时可以停止检查这一层后面的所有候选数？

参考答案

1. 不同的组合为 `[2, 3]` 和 `[5]`。

2. 本题把 `[2, 3]` 和 `[3, 2]` 看作同一种组合，数字的选择顺序不计入答案。 规定路径中的数字从小到大出现，就能在搜索时直接跳过 `[3, 2]` 这类重复组合。

3. 当前还差 2，而候选数 3 已经大于 2。因为数组已经排好序， 3 后面的候选数只会更大，也都不可能加入当前组合，所以可以直接结束这一层的检查。

### 3. 下一枚皇后可以放在哪些位置

在一个 `4 × 4` 棋盘上按行放置皇后，行、列下标都从 0 开始。 目前已经在 `(0, 1)` 和 `(1, 3)` 放置了皇后，现在要在第 2 行放置下一个皇后。

1. 哪些列会因为“同列”而被排除？
2. 在剩余列中，哪些位置会因为“同一条对角线”而被排除？
3. 第 2 行还剩哪些位置可以尝试？

参考答案

1. 第 1 列和第 3 列已经有皇后，因此位置 `(2, 1)` 和 `(2, 3)` 被排除。

2. 在剩余位置中，`(2, 2)` 与 `(1, 3)` 位于同一条对角线上，因此也被排除。 位置 `(2, 0)` 与已有两个皇后都不在同列或同一条对角线上。

3. 第 2 行可以尝试的位置只有 `(2, 0)`。

   这一步只说明当前放置合法；之后若无法完成棋盘，仍需回退并尝试更早的其他选择。

## 13.6.2 编程练习

### 1. 无重复元素的全排列

整数数组 `nums` 至少包含一个元素，并且其中各元素互不相同。 请列出把这些元素各使用一次所能形成的全部顺序，并将每一种顺序作为一个数组返回。 结果中各排列的先后次序不作要求。 请使用回溯，并用布尔数组记录每个位置的元素是否已经选入当前排列。

解题提示

1. 递归深度表示正在填写排列中的第几个位置
2. 每一层只尝试尚未使用的元素
3. 路径长度达到 `nums` 的长度时，把它的副本加入答案

LeetCode 题目解析

> 说明： 链接题解通过交换数组元素，把已选元素依次放到数组前部；本练习使用布尔数组记录每个元素是否已选。两种方法都能避免同一元素被重复选择，但代码结构不同

##### 欢迎在评论区留下你的见解、问题或建议