定义

引用自百度百科:

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

回溯算法实际上是对所有结果的一种暴力枚举方法,以走迷宫为例,它尝试走每条路径,一旦路径不通则退回到最近的分岔点,继续尝试下一条路径,如此反复,直到找到一条正确的路径,或者走完所有路径。对于诸如八皇后、数独这类往往需要枚举所有可能性方案的问题,使用回溯算法再合适不过了。回溯算法采用递归的方式去遍历所有可能结果,时间复杂度高达$ O(n!) $,一般需要伴随“剪枝”操作,以应对庞大的时间复杂度。

假设是走迷宫,这个回溯算法的模板应该是这样:

def backtrace(path,depth,length):
if depth==length:
#路径结束(走到头),验证结果
return
for node in nodes:
#枚举所有分岔口可能的节点,加入到路径中
path.append(node)
#路径增长,继续下一轮
backtrace(path,depth+1,length)
#移除当前节点,准备试下一个
path.pop(node)

基础题:组合

力扣官方:77.组合

给定两个整数 nk,返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

组合是枚举所有的数字,并不涉及到顺序,所以我们只需要从[1-n]挨个选取数字,在之后的回溯中,只选取起始数字往后的数字。我们定义的回溯方法backtrace包含2个参数,参数i表示当前的起始数字,作为可选数字的下限,i之前的数字表示已经选择过,不再重复选择,所以ji开始遍历;参数arr是一个临时数组,用于存储一个组合的结果,一旦组合中数字的个数达到题目要求的k,表示已确定一个组合,将其归到结果中。这里需注意,数组是一个引用类型,在纳入结果集的过程中,需使用拷贝的新对象res.append(arr[:]),否则你在回溯的过程中会改变原先已纳入结果集的数组,因为操作的是同一个对象。

def combine(self, n: int, k: int) -> List[List[int]]:
res=[]
def backtrace(i,arr):
if len(arr)==k:
res.append(arr[:])
return
for j in range(i,n+1):
arr.append(j)
backtrace(j+1,arr)
arr.pop()
backtrace(1,[])
return res

回溯算法可以看作是对一棵树的深度优先遍历(dfs),其中树的每一层节点就对应着代码中的for j in range(i,n+1)循环。

优化:可以注意到,我们是没必要遍历到数字4的,因为到数字4之后就没有数字可选了,是没办法凑齐到题目要求的2个数字的,所以我们可以根据当前组合大小以及需要凑齐的个数k确定可选数字的上限是什么,让可选数字的上界从n变成n-(k-len(arr)-1)

def combine(self, n: int, k: int) -> List[List[int]]:
res=[]
def backtrace(i,arr):
if len(arr)==k:
res.append(arr[:])
return
for j in range(i,n+1-(k-len(arr)-1)): #剪枝
arr.append(j)
backtrace(j+1,arr)
arr.pop()
backtrace(1,[])
return res

这里以从4个数字选取3个为例,你可以看到加上这个条件之后达到的剪枝效果,避免了无意义的枚举。红色的箭头表示我们剪掉的位置,不会再进行后续的遍历。

基础题:排列

无重复数的排列

力扣官方:46.全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

排列与组合的不同之处在于,排列不仅要选择出数字,而且还需要关注数字的所在顺序,而组合是不关注排列顺序的。比如对于[1,2,3][3,2,1]来说,这2者算作同一个组合,因为它们都具备同样的3个数字1,2,3,而这2者不能算作同一个排列,因为3个数字的顺序不一样。

在排列中,不可从起始数字开始枚举,或者说排列是没有起始数字的,每次必须从头开始遍历for j in range(n),因为排在后面的数字可能被取到前面,而在组合中,由于不在乎顺序,所以我们从前往后取即可。排列不一样,每个数字都有可能被第一次选到(处于位置0),所以在排列中,我们必须额外记录数字是否被取用,你可以直接在arr中判断是否存在某数,但这将耗费$ O(n) $的时间复杂度(遍历整个数组),常规办法是采用空间换时间的方式,用一个used数组记录数字是否被选用,它存储的状态和arr中的元素保持一致,当arr发生改变时,同步维护used的状态。当数字存在arr中时,used标记该数字为true,反之,标记该数字为false

由于是对序列进行全排列,我们统一用索引来代替具体的数字。

def permute(self, nums: List[int]) -> List[List[int]]:
n=len(nums)
res=[]
used=[False]*n
def backtrace(i,arr):
if i==n:
res.append(arr[:])
return
for j in range(n):
if used[j]:
continue
used[j]=True
arr.append(nums[j])
backtrace(i+1,arr)
arr.pop()
used[j]=False
backtrace(0,[])
return res

有重复数的排列

力扣官方:47.全排列II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

该题与上一题不同之处是序列中包含了重复的数字,而重复的数字得到的排列应该去重。比如对于无重复数序列[1,2,3],可以得到的排列个数为3*2*1=6,而有重复数序列[1,1,2]得到的6个排列中,会得到2个[1,1,2](第1个1和第2个1位置不同的排列),这里面只能保留一个结果。

为了满足这一条件,我们在回溯过程中就进行剪枝操作,为了更容易比较重复数,第1步先对数组进行排序,这样重复数全部排在了一起;第2步除了判断当前数是否使用if used[j]剪枝外,继续对重复数进行剪枝if j>0 and nums[j]==nums[j-1] and not used[j-1],如果前一个重复的数字还没用过,则优先前面的排列,该分支被剪掉。

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort() #将序列排序
n=len(nums)
res=[]
used=[False]*n
def backtrace(i,arr):
if i==n:
res.append(arr[:])
return
for j in range(n):
if used[j]:
continue
if j>0 and nums[j]==nums[j-1] and not used[j-1]: #剪枝:前一个重复的数字还没用过
continue
used[j]=True
arr.append(nums[j])
backtrace(i+1,arr)
arr.pop()
used[j]=False
backtrace(0,[])
return res

应用题:组合总和

无重复数任意长度组合总和

力扣官方:39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

输入:candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

此题和之前的基础题组合,有2个区别:

  1. 基础题组合的回溯退出条件是组合数量达到目标值,该题的回溯退出条件是组合总和等于目标值;
  2. 组合中的数字可以无限重复选用

所以我们这里相比于普通组合,需要做以下改动,回溯函数增加t参数,用于记录当前已累加的总和,回溯函数的返回改为判断是否超出目标值,当大于或者等于目标值后不再进行回溯(后续和只会增大,不会再产生满足要求的结果),如果等于目标值则我们找到一个答案;由于数字可以重复选用,所以相比于普通组合的backtrace(j+1,arr),进入回溯仍然从j开始,backtrace(j,arr,t+candidates[j])

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res=[]
n=len(candidates)
def backtrace(i,arr,t):
if t>=target:
if t==target:
res.append(arr[:])
return
for j in range(i,n):
arr.append(candidates[j])
backtrace(j,arr,t+candidates[j]) #继续从j开始回溯
arr.pop()
backtrace(0,[],0)
return res

以candidates = [2,3,5], target = 8为例,以下就是回溯路径,当组合总和大于等于目标值8时回溯返回,标蓝的叶子节点表示总和正好等于目标值,标红的叶子节点表示总和超过目标值。

优化:不难发现,在回溯的for循环中,如果当前节点已经超过了目标值,后续的循环都是没有必要的,因为总和一定会比当前的还大,不过这个需要一个前提就是序列是按升序排列的。我们可以先花费$ nlog(n) $的时间复杂度对序列排序,进而就可以在此基础上进行剪枝操作。

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res=[]
n=len(candidates)
candidates.sort() #排序
def backtrace(i,arr,t):
if t==target:
res.append(arr[:])
return
for j in range(i,n):
if t+candidates[j]>target: #剪枝
break
arr.append(candidates[j])
backtrace(j,arr,t+candidates[j])
arr.pop()
backtrace(0,[],0)
return res

可以看到,我们把判断大于目标值的逻辑移到了for循环中,一旦出现大于目标值则直接退出循环,后续的节点不会再次进入回溯,实现剪枝效果。所谓剪枝,就是减少回溯的路径,图像表示为从树中剪去枝干。

有重复数任意长度组合总和

力扣官方:40.组合总和II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

  • 所有数字(包括目标数)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

此题与上一题的区别是,数组中包含重复的元素,同时每个数组中的元素只能选择一次,只能选择一次这个条件在代码中体现为backtrace(j+1,arr,t+candidates[j]),即从下一个位置开始回溯。由于存在重复的元素,为了避免产生重复的组合,我们可以采用前面讲无重复排列时相同的办法:先对数组进行排序,之后根据当前数字和前一个数字是否相同判断是否重复组合。由于数组已经排序,我们可以继续使用上一题的剪枝方法。

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res=[]
n=len(candidates)
candidates.sort()
def backtrace(i,arr,t):
if t==target:
res.append(arr[:])
for j in range(i,n):
if t+candidates[j]>target: #剪枝:去除无意义的路径
break
if j>i and candidates[j]==candidates[j-1]: #剪枝:去除重复的组合
continue
arr.append(candidates[j])
backtrace(j+1,arr,t+candidates[j])
arr.pop()
backtrace(0,[],0)
return res

以candidates = [1,1,2], target = 2为例,我们最终只会得到[1,1][2]二种结果。

无重复数指定长度组合总和

力扣官方:216.组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

该题可以看作是在数组[1,2,3,4,5,6,7,8,9]中选择k个数,其和要等于n,根据题目意思我们可以得到3个信息:

  1. 数组是有序的(可以剪枝)
  2. 每种组合中不存在重复的数字(每个数字只能使用一次,回溯要从下一个数字开始backtrace(j+1,...)
  3. 数组中的每个数字都不重复(对于解集不能包含重复组合的约束,我们无须进行排重剪枝)
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res=[]
def backtrace(i,arr,t):
if len(arr)==k:
if t==n:
res.append(arr[:])
return
for j in range(i,10):
if j+t>n: #剪枝
break
arr.append(j)
backtrace(j+1,arr,t+j)
arr.pop()
backtrace(1,[],0)
return res

总结

  1. 对于有重复数的排列或者组合,我们需要先对数组进行排序,让相同的数排在一起,进而方便排重
  2. 排列涉及到顺序,每个位置都可以是所有数字,所以每次从头开始选取数字for j in range(n);组合不涉及顺序,所以我们依次选择,选取时会从起始位置开始for j in range(i,n)
  3. 对于数字是否可以重复选用,决定回溯时是从当前位置或是下一个位置:backtrace(j,...)backtrace(j+1,...)
  4. 对于求组合总和问题(每个数字都是正整数,和越加越大),可以先将数组排序,然后进行剪枝优化