13.6 练习¶
13.6.1 知识巩固¶
1. 这段排列算法会漏掉结果吗¶
一个回溯算法按 1、2、3 的顺序尝试生成全部排列。每次选择数字 x 时，它会：
- 把
x加到当前路径末尾； - 把
x标记为“已使用”； - 递归填写下一个位置。
递归返回后，同学只从路径末尾删除了 x，然后继续尝试下一个数字。
- 算法首先得到哪个排列？它还能得到全部 6 个排列吗？
- 递归返回上一层前，只删除路径末尾的数字是否足够？如果不够，还需要做什么？说明理由。
参考答案
-
它首先得到
[1, 2, 3]，但无法得到全部排列。虽然返回时路径变短了， 数字 1、2、3 的标记仍都是“已使用”，后续分支便没有可选数字。 -
不够。删除路径末尾的
x后，还必须把x重新标记为“未使用”。 当前路径和已使用标记共同描述搜索状态；选择时修改了两处，回退时也必须把两处都恢复， 其他分支才能再次选择x。
2. 数字的选择顺序重要吗¶
给定排好序的数组 [2, 3, 5] 和目标值 5，每个数可以重复选择。
算法规定每条搜索路径中的数字只能按从小到大的顺序出现。
- 能得到哪些不同的组合？
- 为什么同一组数字不需要按不同顺序重复搜索？“从小到大”的限制起到了什么作用？
- 当前路径为
[3]、还差 2 时，下一个候选数是 3。为什么此时可以停止检查这一层后面的所有候选数？
参考答案
-
不同的组合为
[2, 3]和[5]。 -
本题把
[2, 3]和[3, 2]看作同一种组合，数字的选择顺序不计入答案。 规定路径中的数字从小到大出现，就能在搜索时直接跳过[3, 2]这类重复组合。 -
当前还差 2，而候选数 3 已经大于 2。因为数组已经排好序， 3 后面的候选数只会更大，也都不可能加入当前组合，所以可以直接结束这一层的检查。
3. 下一枚皇后可以放在哪些位置¶
在一个 4 × 4 棋盘上按行放置皇后，行、列下标都从 0 开始。
目前已经在 (0, 1) 和 (1, 3) 放置了皇后，现在要在第 2 行放置下一个皇后。
- 哪些列会因为“同列”而被排除？
- 在剩余列中，哪些位置会因为“同一条对角线”而被排除？
- 第 2 行还剩哪些位置可以尝试？
参考答案
-
第 1 列和第 3 列已经有皇后，因此位置
(2, 1)和(2, 3)被排除。 -
在剩余位置中，
(2, 2)与(1, 3)位于同一条对角线上，因此也被排除。 位置(2, 0)与已有两个皇后都不在同列或同一条对角线上。 -
第 2 行可以尝试的位置只有
(2, 0)。这一步只说明当前放置合法；之后若无法完成棋盘，仍需回退并尝试更早的其他选择。
13.6.2 编程练习¶
1. 无重复元素的全排列¶
整数数组 nums 至少包含一个元素，并且其中各元素互不相同。
请列出把这些元素各使用一次所能形成的全部顺序，并将每一种顺序作为一个数组返回。
结果中各排列的先后次序不作要求。
请使用回溯，并用布尔数组记录每个位置的元素是否已经选入当前排列。
解题提示
- 递归深度表示正在填写排列中的第几个位置
- 每一层只尝试尚未使用的元素
- 路径长度达到
nums的长度时，把它的副本加入答案
说明： 链接题解通过交换数组元素，把已选元素依次放到数组前部；本练习使用布尔数组记录每个元素是否已选。两种方法都能避免同一元素被重复选择，但代码结构不同