LeetCode专题——详解搜索算法中的搜索策略和剪枝
TechFlow2019 人气:1今天是LeetCode专题第20篇文章，今天讨论的是数字组合问题。
描述
给定一个int类型的候选集，和一个int类型的target，要求返回所有的数字组合，使得组合内所有数字的和刚好等于target。
注意：
所有的元素都是正数 所有元素没有重复 答案不能有重复 每一个元素可以使用若干次
样例 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
样例 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题解
我们拿到这道题还是按照老规矩来思考暴力的解法，但是仔细一想会发现好像没有头绪，没有头绪的原因也很简单，因为题目当中的一个条件：一个元素可以随意使用若干次。
我们根本不知道一个元素可以使用多少次，这让我们的暴力枚举有一种无从下手的感觉。如果去掉这个条件就方便多了，因为每个元素只剩下了两个状态，要么拿要么不拿，我们可以用一个二进制的数来表示。这就引出了一个常用的表示状态的方法——二进制表示法。
二进制表示法
举个例子，假如当下我们有3个数字，这3个数字都有两个状态选或者不选，我们想要枚举这3个数字的所有状态，应该怎么办？
我们当然可以用递归来实现，在每层递归当中做决策当前元素选或者不选，分别递归。但是可以不用这么麻烦，我们可以用二进制简化这个过程。这个原理非常简单，我们都知道在计算机二进制当中每一个二进制位只有两个状态0或者1，那么我们就用1表示拿，0表示不拿，那么这三个数拿或者不拿的状态其实就对应一个二进制的数字了。3位二进制，对应的数字是0到7，也就是说我们只需要遍历0到7，就可以获得这3位所有拿和不拿的状态了。
比如说我们当下遍历到的数字是5，5的二进制表示是101，我们再把1和0对应拿和不拿两种状态。那么5就可以对应上第一和第三个拿，第二个不拿的状态了。我们可以用位运算很方便地进行计算。比如我们要判断第i位是否拿了，我们可以用(1 << i)，<<的意思是左移，左移一位相当于乘2，左移n位就相当于乘上了2的n次方。1对应右边起第0位，也就是最低位的二进制位，我们对它做左移i的操作就相当于乘上了，那么就得到了第i位了。我们拿到了之后，只需要将它和状态state做一个二进制中的与运算，就可以得到state中第i位究竟是0还是1了。
因为在二进制当中，and运算会将两个数的每一位做与运算，运算的结果也是一个二进制数。由于我们用来进行与运算的数是(1 << i)，它只有第i位为1，所以其他位进行与运算的结果必然是0，那么它和state进行与运算之后，如果结果大于0，则说明state的第i位也是1，否则则是0。这样我们就获取了state当中第i位的状态。
由于位运算是指令集的运算，在没有指令集优化的一些语言当中，它的计算要比加减乘除更快。除了快以外它最大的好处是节省空间和计算方便，这两个优点其实是一体的，我们一个一个来说。
首先来说节省空间，有了二进制表示之后，我们可以用一个32位的int来代表32个物体的0和1的所有状态。如果我们用数组来存储的话，显然我们需要一个长度为32的数组，需要的空间要大得多。这一点在单个状态下并不明显，一旦数据量很大会非常显著。尤其是在密集的IO当中，数据越轻量则传输效率越高。
第二个优点是计算方便，计算方便的原因也很简单，假如我们要遍历所有的状态，如果用数组或者其他数据结构的话免不了使用递归来遍历，这样会非常麻烦。而使用二进制之后就方便了，由于我们用二进制表示了所有元素0和1的状态，我们只需要在一个整数范围做循环就可以了。就像刚才例子当中，我们要枚举3个元素的状态，我们只需要从0遍历到7即可。如果在多点元素也没问题，如果是N个元素，我们只需要从0遍历到(1 << N) - 1。
但是还有一个问题没解决，你可能会说如果我们用int来表示状态的话，最多只能表示32个物品的状态，如果更多怎么办？一个方法是使用int64，即范围更大的int，如果范围更大的int还是解决不了问题也没关系，还有一些基于同样原理实现的第三方包可以支持。但是老实说我们基本上不会碰到超过64个物品让我们枚举所有状态的情况，因为这个数字已经非常大了，几乎可以说是天荒地老也算不完。
回到问题
我相信关于二进制表示法的使用和原理，大家应该都了解了，但是本题当中元素是可以多次出现的，二进制表示法看起来并不顶用，我们怎么解决这个问题呢？难道这么大的篇幅就白写了？
当然不会白写，针对这种情况也有办法。其实很简单，因为题目当中规定所有的元素都是正数，那么对于每一个元素而言，我们最多取的数量是有限的。举个例子，比如样例当中[2, 3, 6, 7] target是7，对于元素2而言，target是7，即使可以多次使用，也最多能用上3个2。那么我们可以拓充候选集，将1个2拓充成3个，同理，我们可以继续拓充3，最后候选集变成这样：[2, 2, 2, 3, 3, 6, 7]，这样我们就可以使用二进制表示法了。
但是显然这个方法不靠谱，因为如果数据当中出现一个1，并且target稍微大一些，那肯定直接gg，显然会复杂度爆炸。所以这个方法只是理论上可行，但是实际上并不具有可操作性，我之所以拿出来介绍，纯粹是为了引出二进制表示法。
搜索解决一切
当一个问题明显有很多种情况需要遍历，但是我们又很难直接遍历的时候，往往都是搜索问题，我们可以思考一下能否用搜索问题的方法来解决。
这题其实已经非常明显了，搜索的条件已经有了，搜索的空间也明白了，剩下的就是制定搜索策略。
我个人认为搜索策略其实就是搜索的顺序和范围，合适的搜索顺序以及范围可以大大降低编码和计算的复杂度，再穿插合适的剪枝，就可以非常漂亮地完成一道搜索问题。
我们带着思考来看这道题，如果我们用回溯法来写这道题的话，代码其实并不复杂。很容易就可以写出来：
def dfs(x, sequence, candidates, target):
if x == target:
ans.append(sequence)
return
for i in candidates:
if x + i > target:
continue
sequence.append(i)
dfs(x+i, sequence, candidates, target)
sequence.pop()
你看只有几行，我们每次遍历一个数加在当前的总和x上然后往下递归，并且我们还加上了对当前和判断的剪枝。如果当前和已经超过了target，那么显然已经不可能构成正解了，我们直接跳过。
但是我们也都发现了，在上面这段代码里，我们搜索的区间就是所有的候选值，我们没有对这些候选值进行任何的限制。这其实隐藏了一个很大的问题，还记得题目的要求当中有一条吗，答案不能有重复。也就是说相同元素的不同顺序会被认为是同一个解，我们需要去重。举个例子，[3, 2, 2]和[2, 2, 3]会被认为是重复的，但是在上面的搜索策略当中，我们没有对这个情况做任何的控制，这就导致了我们在找到所有答案之后还需要进行去重的工作。先找到包含重复的答案，再进行去重，这显然会消耗大量计算资源，所以这个搜索策略虽然简单，但远远不是最好的。
我们先来分析一下问题，究竟什么时候会出现重复呢？
我想大家列举一下应该都能发现，就是当我们顺序错乱的时候。比如说我们有两个数3和4，我们先选择3再选择4和先选择4再选择3是一样的。如果我们不对3和4的选择做任何限制，那么就会出现重复。换句话说如果我们对3和4的选择确定顺序就可以避免重复，如果从一开始就不会出现重复，那么我们也就没有必要去重了，这就可以节省下大量的时间。
所以我们要做的就是确定搜索的时候元素选择的顺序，在搜索的时候进行一定的限制，从而避免重复。落实在代码当中就体现在我们枚举候选集的时候，我们之前没有做任何限制，我们现在需要人为加上限制，我们只能选择之前选过的元素后面的，只能往后拿不能往前拿。所以我们需要在dfs当中传入一个下标，标记之前拿过的最大的下标，我们只能拿这个下标之后的，这样搜索就有了顺序，就避免了元素重复和复杂度过高的问题。
这一点确定了之后，剩下的代码就很简单了。
class Solution:
def dfs(self, ret, pos, sequence, now, target, candidates):
if now == target:
# 加入答案，需要.copy()一下
ret.append(sequence.copy())
return
for i in range(pos, len(candidates)):
# 如果过大则不递归
if now + candidates[i] > target:
continue
# 存入sequence，往下递归
sequence.append(candidates[i])
self.dfs(ret, i, sequence, now+candidates[i], target, candidates)
sequence.pop()
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret = []
self.dfs(ret, 0, [], 0, target, candidates)
return ret
从代码上来看，我们并没有做太大的改动，所有的细节几乎都体现在搜索和遍历时的边界以及控制条件上。和整个算法以及代码逻辑比起来，这些是最无关紧要的，但是对于解决问题来说，这些才是实实在在的。
题目变形
今天的题目有一个变种，它就是LeetCode的第40题，大部分题意都一样，只有两个条件发生了变化。第一是40题当中去掉了候选集当中的元素没有重复的限制，第二点是不再允许元素重复使用。其他的内容都和这题保持一致。
我们想一下就会发现，如果我们去掉重复使用的条件，好像没什么变化，我们是不是只要将递归遍历的条件稍稍改动就好了呢？之前我们是从pos位置开始化后遍历，现在由于不能重复，所以之前取过的pos不能再取，我们是不是只要将for循环改成从pos+1开始就行了？
如果候选集的元素中没有重复，这当然是可行的。但是很遗憾，这个条件也被去掉了。所以候选集当中本身就可能出现重复，如果还按照刚才的思路会出现重复的答案。
原因也很简单，举个例子，比如说候选集是[1, 2, 3, 2, 2]，target是5，如果还用刚才的方法搜索的话，我们的答案当中会出现两个[2, 3]。虽然我们也是每个元素都只用了一次，但是仍然违背了答案不能重复的限制。
你可能会有很多想法，比如可以手动去重，比如我们可以在元素数量上做手脚，将重复的元素去重。很遗憾的是，两者都不是最优解。第一种当然是可行的，找到所有可行解再去重，是一个很朴素的思路。通过优化，可以解决复杂度问题。第二种想法并不可行，因为如果我们把重复的元素去掉，可能会导致某些解丢失。比如[1, 2, 2]，也是和等于5，但是如果我们把重复的2去掉了，那么就无法得到这个解了。
要解决问题，我们还是要回到搜索策略上来。手动筛选、加工数据只是逼不得已的时候用的奇淫技巧，搜索策略才是解题的核心。
我们整理一下思路，可以归纳出当前需要我们解决的问题有两个，第一个是我们要找到所有解，意味着我们不能删减元素，第二个是我们想要搜索的结果没有重复。这看起来是矛盾的，我们既想要不出现重复，又想重复的元素可以出现，这可能吗？
如果你仔细思考分析了，你会发现是可能的。不过从搜索策略的角度上来说，比较难想到。首先我们要保证元素的聚集性，也就是说相同的元素应该聚集在一起。要做到这点很简单，我们只需要排序就行了。这么做的原因也不难想到，就是为了避免重复。如果数据是分散的，我们是很难去重的，还用刚才的例子，当我们从2开始递归的时候，我们可以找到解[2, 3]，当我们从3开始递归的时候，我们仍然可以找到解[3, 2]，这两者是一样的。虽然我们限制了遍历的顺序严格地从前到后，但是由于元素分散会使得我们的限制失去作用。为了限制依旧有效，我们需要排序，让相同的元素聚集，这样我们每次搜索的内容其实是由大于等于当前元素的数字组成的答案，这就保证了不在重复。
但是这并没有解决所有的问题，我们再来看一个例子，候选集是[2, 2, 2, 3, 4]，target是7，显然[2, 2, 3]是答案，但是我们怎么保证[2, 2, 3]只出现一次呢？因为我们有3个2，但是要选出两个2来，我们需要一个机制，使得只会找到一个答案。这点通过策略已经无能为力了，只能依靠剪枝。我们当然可以引入额外的数据结构解决问题，但会比较麻烦，而我们其实有更简单的做法。
这个做法是一个非常精妙的剪枝，我们在递归当中加入一个判断：当i > pos+1 and candidates[i] == candidates[i-1]的时候，则跳过。其中pos是上次选择的位置，在递归的起始时，带入的是-1，我想这个条件应该大家都能看明白，但是它为什么有效可能会一头雾水，翻译成大白话，这个条件其实是在限制一点：在有多个相同元素出现的时候，必须选择下标小的，也就是前面的。
我们分析一下可能触发continue的条件，只有两种情况，第一种：
其中pos是上次选择的数字，我们假设它是1，我们当前的位置在pos+3。从上图可以看出来，pos+1到pos+3全都相等。如果我们想要选择pos+3而跳过pos+1和pos+2则会进入continue会跳过。原因也很简单，因为前面递归的过程当中已经选过pos和pos+1的组合了，我们如果选了pos和pos+3的组合一定会构成重复。也就是说我们保证了在连续出现的元素当中，如果要枚举的话，必须要从第一个开始。
另一种情况也类似：
也就是说从pos到pos+3都是2，都相等，这个时候我们跳过pos+1和pos+2直接选择pos+3也会进入continue，原因也很简单，我们现在枚举的是获取两个2的情况，在之前的递归当中已经没举过pos和pos+1了，我们现在想要跳过pos+1和pos+2直接获取pos+3，对应的情况是一样的，所以需要跳过。
我们将排序和上述的剪枝方法一起使用就解出了本题，仔细观察一下会发现这两个方法根本是相辅相成，天作之合，单独使用哪一个也不管用，但是一起作用就可以非常简单地解出题目。理解了这两点之后，代码就变得很简单了：
class Solution:
def dfs(self, ret, sequence, now, pos, target, candidates):
if now == target:
ret.append(sequence.copy())
return
for i in range(pos+1, len(candidates)):
cur = now + candidates[i]
# 剪枝
# 如果多个相同的元素，必须保证先去最前面的
if cur > target or (i > pos+1 and candidates[i] == candidates[i-1]):
continue
sequence.append(candidates[i])
self.dfs(ret, sequence, cur, i, target, candidates)
sequence.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 排序，保证相同的元素放在一起
candidates = sorted(candidates)
ret = []
self.dfs(ret, [], 0, -1, target, candidates)
return ret
不知道大家有没有从这个变种当中感受到搜索策略以及剪枝的威力和巧妙，我个人还蛮喜欢今天的题目的，如果能够把今天的两道题目吃透，我想大家对于深度优先搜索和回溯算法的理解一定可以更上一个台阶，这也是我将这两个问题合在一起介绍的原因。在明天的LeetCode专题当中我们会来看LeetCode41题，查找第一个没有出现的自然数。
今天的文章就到这里，如果觉得有所收获，请顺手点个关注吧，你们的举手之劳对我来说很重要。
本文使用 mdnice 排版
加载全部内容