力扣刷题笔记 #10 搜索&剪枝

本文最后更新于：2023年3月18日晚上

本文包含「搜索&剪枝」类型题中的：搜索回溯、优化剪枝、A* 搜索、启发式搜索等。持续更新中。

题目描述：
方法1：
方法2：
方法3：
坑点：

搜索回溯

暴力搜索 + 回溯，常见于「返回所有可能组合、方案、排列」题目，由于要得到所有可能，就必须暴力搜索，最多加上一定的优化剪枝。

回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置。

function<void(int)> dfs = [&](int now){
    if(now == n){
        // 生成答案，回溯
        return;
    }
    for(int i = 0; i < n; i++){
        if(vis) continue; // 剪枝
        // 此处要进入下一个状态
        dfs(now + 1); // 搜索
        // 此处要恢复上一个状态
    }
};
dfs(0);

17. 电话号码的字母组合 (M)

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的九键字母组合。答案可以按任意顺序返回。

方法1：DFS 回溯，递归时用参数 $now$ 表示遍历到第几个数字；当 $now=n$ 时递归结束，加入答案数组。时间复杂度 $O(3^n)$，空间复杂度为递归栈的深度 $O(n)$。

方法2：BFS + 队列，每遍历到一个数字，就把队列中所有元素依次弹出，尾部加上不同字母后再压回队列。最后整个队列存放的就是答案。

22. 括号生成 (M)

题目描述：数字 n 代表目标字符串中合法括号的对数，生成所有可能的并且合法的括号组合字符串。

方法1：DFS 回溯，定义用一个 $cur$ 全局字符串，每次 DFS 时如果 $左括号数<n$，则在末尾添加一个 ( 继续 DFS；如果 $右括号数<左括号数$，则在末尾添加一个 ) 继续 DFS，当 $cur.size()=2n$ 时结束。

时刻保持 $右括号数 \leqslant 左括号数 \leqslant n$，则能够保证左括号先放置，则序列一定合法。

方法2：递归调用自身，递归 f(n-1) 得到对数 $n-1$ 的答案，并在每一个位置插入 ()，去重后得到答案。

最终答案包含元素个数可以证明是第 $n$ 个卡特兰数 $\frac{1}{n+1}C^{n}_{2n}$，渐进于 $\frac{4^n}{n\sqrt{n}}$。而在回溯过程中，每个字符串需要 $O(n)$ 的时间插入新的括号，并 $O(1)$ 移动到新数组，所以总时间复杂度为 $O($$ )$。
而总共的递归层数为 $n$，每层都需要一个与答案数组同样数量级的临时数组，所以总空间复杂度也为 $O($$ )$。

方法3：记忆化 DFS，答案序列的第一个字符一定是 (，与之对应的 ) 可能出现在右侧任何一个位置，构成 (A)B。枚举 ) 的位置 $2i+1$，则 A 就是 f(i)，B 就是 f(n-i-1)，记忆化存储每个结果，遍历拼接。

39. 组合总和 (M)

题目描述：给定一个无重复整数数组，和一个目标整数，找出数组中所有和为目标数的元素组合，同一个数字可以无限次重复选中，如果至少一个数字的被选数量不同，则两种组合是不同的。

方法1：DFS 回溯，用一个临时序列记录。递归时记录当前距离目标的差值和当前可选的数字起点，每次递归可以选择跳过当前数并将起点向前移动，也可以选择当前数且不移动起点，递归回溯后要将当前数移出临时序列。当起点遍历完时递归结束，当差值为零时得到组合。

方法2：DFS + 剪枝，先将数组从小到大排序，则当一个数字选完可能会溢出时，其后面的数字也不会再选，提前结束。

46. 全排列 (M)

题目描述：给定一个无重复整数数组，返回其所有可能的全排列，可以按任意顺序返回。

方法1：使用「31. 下一个排列」中的方法，每次都「贪心」找出下降点，时间复杂度 $O(n\times n!)$。

方法2：DFS 回溯，用一个临时序列记录，由于不按顺序，每次可从剩余数中放入一个数继续递归，递归回溯后要将当前数移出临时序列。时间复杂度 $O(n\times n!)$。

记录剩余数的方法有很多：
枚举下一个数，同时比对其是否出现在临时序列（无重复的好处）；
用一个 $vis$ 数组记录临时序列中的数，作为参数传递，进一步地，可以用状态压缩；
使用一个分割点，左侧的数作为已确定的，右侧的数是将要访问的，每次从右侧 swap 一个数到分割点的位置，继续递归，递归回溯后将其 swap 回原位。

47. 全排列 II (M)

题目描述：给定一个有重复整数数组，返回其所有不重复的全排列，可以按任意顺序返回。

方法1：DFS 回溯，用一个临时序列记录，每次从剩余数中放入一个数继续递归，但是还需要判断相同数不能多次放置在当前位置。先排序将相同数放到一起，再用以下条件判断：

1
2
3

if(vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) continue;
// !vis[i - 1] 用于限制两个相邻的重复数字的访问顺序
// 例如 1 1，只有当前面的 1 访问过才会访问后面的 1，确保不会出现两次 1 1

坑点：本题不能用上一题记录剩余数的方法 1，因为有重复；不能用方法 3，因为 swap 会打乱右侧数的顺序，使相同数不再放到一起。

78. 子集 (M)

题目描述：给定一个整数数组，数组中的元素互不相同 。返回该数组所有可能的子集（幂集）。

方法1：枚举，每个数有两种选择，总共有 $2^n$ 个子集，用二进制表示每个子集，则范围是 $[0, 2^n-1]$。枚举每个数字并生成对应的子集，时间复杂度 $O(n \cdot 2^n)$。

方法2：DFS 回溯，用一个临时序列记录，每次将 $now$ 指向的数「放入或不放入」后继续递归，递归回溯后要将放入的数移出临时序列。时间复杂度 $O(n \cdot 2^n)$。

方法3：线性 DP，$dp[i]$ 表示前 $i$ 个数的子集，初始 $dp[0]$ 为空集，每遍历到一个数就将前面的所有子集拼接上这个数，然后放入 $ans$。时间复杂度 $O(n \cdot 2^n)$。 \[ dp[i]=dp\left[ i-1 \right] +dp\left[ i-1 \right] \oplus nums\left[ i \right] \]

优化剪枝

有的搜索问题涉及排列组合、卡特兰数等内容，暴力复杂度达到 $O(n!)$ 或 $O(k^n)$，必须使用优化、剪枝技巧。二者有一定的相似性。

所谓优化，就是降低单轮判断的复杂度，常用的优化技巧有：

记忆化，通过记录出现过的子状态，来快速判断当前状态的有效性；
辅助数组，以空间换时间，通常记录影响当前局面的历史信息；
编排分支顺序，先解决相对简单的子问题，使其他尚未解决的问题得到简化；
状态压缩，在小范围数据中使用，加快多维数组的访问效率、或减少辅助数组的空间占用。

所谓剪枝，就是提早退出某些搜索分支，常用的剪枝技巧有：

记忆化，对于出现过的子状态，标记 $vis$，防止多次访问；
可行性判断，根据题意提前退出不可能的分支（无法转向目标状态），避免无用的搜索；
最优性判断，每次搜索前判断当前解是否可能超过当前最优解，避免无用的搜索。

51. N 皇后 (H)

题目描述：国际象中，皇后可以攻击与之处在同一行、同一列、同一斜线上的棋子。将 $N$ 个皇后放在 $N\times N$ 的棋盘上，使其彼此之间不能相互攻击，返回所有解决方案。

方法1：暴力，按行搜索，第一行有 $N$ 种选择，第二行有 $N-1$ 种选择，以此类推。对于每个选择，逐个判断和之前放置过的皇后是否冲突，如果不冲突则搜索下一行。时间复杂度 $O(N\times N!)$。

方法2：暴力 + 辅助数组，使用额外的三个数组或哈希集合标记该列、主对角线、副对角线有无皇后，每次可以 $O(1)$ 判断冲突，时间复杂度 $O(N!)$，空间复杂度 $O(N)$。

对角线可以通过存行下标与列下标之差、行下标与列下标之和来表示，注意数组下标不能是负数，需要偏移 $N$，但是哈希集合不需要。

方法3：暴力 + 辅助数组 + 状态压缩，用三个整数的二进制位实现标志，每次先三个数进行或运算，得到 0 的位置就是可以放置的位置，时间复杂度 $O(N!)$，空间复杂度 $O(1)$（不考虑递归的空间占用）。

二进制位的标志 0 表示的是「该位可以放置」，而不是方法 2 中的「列、主对角线、副对角线」，因此在搜索时，下一行的应为 dfs(n, row+1, col|pos, (ld|pos)<<1, (rd|pos)>>1);，最后两个参数表示两条对角线带来的影响会左移、右移一位。
求 pos 需要用到位运算技巧 n & (-n) 和 n & (n-1)。

301. 删除无效的括号 (H)

题目描述：给定一个由括号和字母组成的字符串，删除最小数量的无效括号，使得字符串有效。返回所有可能的结果。

方法1：DFS 回溯，合法的方案左右括号数量相等，记左括号为 $+1$，右括号为 $-1$，最终得分必然为 $0$。DFS 正向遍历字符串，考虑每个元素是否放入子串，当遍历结束时，判断最终得分是否为 $0$，如果合法，则考虑将其加入集合去重。由于要求删除最小数量，剩余的字符串应该越长越好，因此维护一个 $maxlen$，仅当子串长度大于等于 $maxlen$ 时将其放入，并且只保留长度等于 $maxlen$ 的结果。时间复杂度 $O(n\cdot 2^n)$。

方法2：分数剪枝，在 DFS 传入参数 $score$，则根据 $score$ 的取值范围可以进行剪枝，提前排除不可能的子串。

在搜索过程中，两种情况可以提前剪枝：
得分为负数，即在子串前缀中右括号数量大于左括号，此时不可能是合法方案。
得分超过上限，这里的上限指的是 min(左括号的数量, 右括号的数量)，上限只有在「合法左括号先全部出现在左边，右边全是右括号」时才出现。因此当子串前缀中出现大量左括号时，不可能是合法方案。
于是，我们可以得到分数的限制范围 $[0, limit]$，$limit$ 可以预处理。

方法3：预处理 $maxlen$ 剪枝，最终目标串的长度可以提前确定为 $n-l-r$，$l$ 为失配左括号数，$r$ 为失配右括号数。正向遍历到左括号时 $l++$，遍历到右括号时 $l--$，如果 $l$ 为零，则 $r++$ 表示右括号失配。