聊一聊回溯算法
原创
一、回溯算法
回溯法（英语：backtracking）是暴力搜寻法中的一种。是一种可以找出所有（或一部分）解的一般性算法
回溯算法类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
和暴力搜寻法区别在于回溯可以通过剪枝策略以及启发式搜索策略提高效率。
要素和策略
所谓剪枝策略，就是判断当前的分支树是否符合问题的条件，如果当前分支树不符合条件，那么就不再遍历这个分支里的所有路径。
所谓启发式搜索策略指的是，给回溯法搜索子节点的顺序设定一个优先级，从该子节点往下遍历更有可能找到问题的解。
回溯法五大要素：选择列表、解空间树、可行解约束条件、剪枝约束条件、
两个重要过程： 选择和撤销选择
示例问题
下面使用 全排列问题来说明上面几个概念。本文所有代码均使用 Golang 实现。
题目描述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例： 输入：nums = [1,1,2] 输出：[[1,1,2],[1,2,1],[2,1,1]]
1. 根据可选列表构建解空间树
2. 设计约束条件剪枝
3. 设计可行解约束条件
上图所展示的就是基于可选列表[1,1,2] 构造的全排列解空间树，其中绿色标记的是满足条件的可行解，红色标记的是剪枝约束掉的解。 自顶向下是一个选择的过程，每一次在选择前需要判断是否已满足可选解，是否满足剪枝约束。
基于本问题的可行解判断条件就是 “当前已选择到的数据量是否和可选列表长度一致”。 比如这里可选列表只有三个元素，从上往下选择到第三个后这就是一个满足条件的可行解。
基于本问题的剪枝约束是 “不包含重复的排列”，当我们已经使用第一个 1 来构建了可选解，那使用第二个 1 再构建一定会得到相同结果。总结的说就是“如果要选择和之前重复的数据，前提是上一个重复数据已被选择”。就是只有重复元素捆绑在一起使用才不会产生重复结果通过解空间树可以发现这个问题。
每一次在选择到一个满足条件的的元素后，便向后继续选择，遇到不满足情况，撤销选择并 回溯到上一个位置。 如下：
我们用一个切片 s := []int{} 来记录选择过程。第一轮选择过程
s =append(s, 1); s =append(s, 1); s =append(s, 2); 选择达到最低部，发现一个可行解进行记录，这里需要回溯到第一个 1进行 1-> 2 -> 1路径的选择，此时 s=(1,1,2) 回退两个元素到 s=(1) 便可以开始下一轮选择。同理得到一个 （1,2,1）的可行解。当 第一个 1 的两条路径选择完毕后，需要回溯到最顶端，此时s=（），选择第二个 1， 进行剪枝判断判断不通过继续回溯到最顶端。实现代码如下：
func permuteUnique(nums []int) [][]int {
//排序是为了把重复数据归并
//也是启发式选择策略
sort.Ints(nums)
n := len(nums)
//存储当前选择路径
per :=[]int{}
//标记元素选择情况
via := make([]bool,n)
//全局变量存储最终可行解。
ans := make([][]int, 0)
//回溯函数
var backtrack func(idx int)
backtrack = func(idx int) {
//可行解约束条件
if idx == n {
ans = append(ans, append([]int(nil),per...))
return
}
//遍历解空间树
for i, v := range nums {
//剪枝约束条件
//当前元素已被选择或者选择到了重复元素时，前面的重复元素必须连带选择
if via[i] || (i>0 && !via[i-1] && nums[i] == nums[i-1]) {
continue
}
//当前元素满足选择条件加入选择队列
per = append(per, v)
//标记选择过的元素的状态
via[i] = true
//递归
backtrack(idx+1)
//撤销选择和标记
via[i] = false
per = per[:len(per)-1]
}
}
backtrack(0)
return ans
}从上面的代码种我们可以总结到一套解决回溯法问题的模板。
1. 定义全局变量记录可行解；
2. 定义backtrack 递归方法，方法种包含如下内容
2.1 可行解判断条件，判断通过加入可行解队列中
2.2 遍历解空间树： 判断剪枝条件 -> 选择 -> 递归 -> 撤销选择
至于启发性策略和临时解队列根据情况看是否需要。
应用场景：回溯法更多的是应用在数学中的排列、组合、子集、编码等问题中。
二、 十道经典题目
全排列 I
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
和前面示例的全排列相比，这里限制了不含重复数字，就是上面的解空间树上所有路径都是满足可行解条件的，但是需要注意在从头选择过程中不能重复选择到自己，所以这里的剪枝约束是“同一元素不可重复选择”。
解空间树：如上示例图所示
可行解约束：选择到列表长度
剪枝约束：同一元素不可重复选择
func permute(nums []int) [][]int {
result := make([][]int, 0)
perm := make([]int, 0)
vis := make([]bool, len(nums))
var backtrack func(idx int)
backtrack = func(idx int) {
if idx == len(nums) {
result = append(result, append([]int(nil), perm...))
return
}
for i := 0; i < len(nums); i++ {
//剪枝
if vis[i] {
continue
}
//选择
perm = append(perm, nums[i])
vis[i] = true
backtrack(idx + 1)
//撤销选择
vis[i] = false
perm = perm[:len(perm)-1]
}
}
backtrack(0)
return result
}组合I
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。示例：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]解空间树：以示例 n=4，k=2 为例，绿色表示可行解，红色为不满足剪枝约束的
从解空间树很容易找到可行解约束和剪枝约束条件。
可行解约束： 当已选择长度等于 k 时，加入可行解队列
剪枝约束：当前选择值应该大于上一次的选择值，否则会产生重复
代码实现
func combine(n int, k int) [][]int {
//可行解队列
ans := make([][]int,0)
per := make([]int,0)
var backtrack func(index int)
backtrack = func(cur int) {
//可行解约束
if len(per) == k {
ans = append(ans, append([]int(nil), per...))
return
}
for i := 0 ; i<= n;i++ {
//剪枝约束
if i < cur {
continue
}
//选择
per = append(per, i)
//向下递归
backtrack(i+1)
//撤销选择，回溯
per = per[:len(per)-1]
}
}
backtrack(1)
return ans
}组合总和
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为target的不同组合数少于150个。
2 <= candidates[i] <= 40
示例
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]解空间树：以示例数据为例，每个节点两个值分别代表选择的数和目标和减去选择值的结果。
绿色代码可行解，红色代码剪枝，蓝色代表发现重复解的剪枝，蓝色部分省略了部分结构。
可行解约束条件：由解空间树可知，目标和最终为0 时的路径为一个可行解。
剪枝约束条件：（1）当 target < min()时，再下一轮不会选到可行解了。
(2) 当 target <0 时，不可能再选择到可行解（这个结论的前提条件是 nums[i]均大于0）
（3）不能产生重复解，所以每一次选择都应该大于等于上一次的选择。
代码实现：
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := make([][]int,0)
perm := []int{}
var backtrack func(begin, target int)
backtrack = func(begin, target int) {
//可行解约束
if target == 0 {
ans = append(ans, append([]int(nil),perm...))
return
}
//剪枝约束（1）
if target < candidates[0] {
return
}
//剪枝约束（2）
if target < 0 {
return
}
for i := 0; i<len(candidates); i++ {
//剪枝约束（3）
if i < begin {
continue
}
//选择
perm = append(perm, candidates[i])
//回溯，需要注意元素可重复使用所以需要从 i 开始
backtrack(i, target-candidates[i])
//撤销选择
perm = perm[:len(perm)-1]
}
}
backtrack(0,target)
return ans
}组合总和 II
给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。
1 <= candidates[i] <= 50
本题和上一题的题目区别有两点：去掉了“无重复元素” 和 增加了“每个数字在组合中只能使用一次”条件。这些条件只会改变剪枝条件的选择，对解空间树而言没有影响。
解空间树： 基于上题的解空间树剪枝去掉重复使用元素的路径。
可行解约束条件：与上题一致，由解空间树可知，目标和最终为0 时的路径为一个可行解。
剪枝约束条件：
（1）当 target < min()时，再下一轮不会选到可行解了。
(2) 当 target <0 时，不可能再选择到可行解（这个结论的前提条件是 nums[i]均大于0）
（3）不能产生重复解，a. 每一次选择都应该大于 (等于) 上一次的选择。b. 遇到重复元素必须同时选择的情况下才可选择
代码示例：
本文很多代码为了便于与前面的分析匹配理解，没有进行代码条件整合。还有需要注意当多个剪枝条件时排列顺序不同性能也由所不同，所以尽把剪枝性能更高的放在前面，但是可行解约束一定要在剪枝之前。
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := make([][]int, 0)
perm := []int{}
via := make([]bool, len(candidates))
var backtrack func(begin, target int)
backtrack = func(begin, target int) {
if target == 0 {
ans = append(ans, append([]int(nil), perm...))
return
}
if target < candidates[0] {
return
}
if target < 0 {
return
}
for i := 0; i < len(candidates); i++ {
if i < begin {
continue
}
if i > 0 && !via[i-1] && candidates[i-1] == candidates[i] {
continue
}
perm = append(perm, candidates[i])
via[i] = true
backtrack(i+1, target-candidates[i])
via[i] = false
perm = perm[:len(perm)-1]
}
}
backtrack(0, target)
return ans
}组合总和 III
找出所有相加之和为
n的k个数的组合，且满足下列条件：只使用数字1到9每个数字 最多使用一次 ，返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
可行解约束条件：由解空间树可知，可行解约束与上题不一致，本题多了对组合元素个数的限制必须是 K，所以本题的可行解条件为，“目标和最终为0 并且选择路径元素数为 k” 为一个可行解。
剪枝约束条件： (1）目标和不可为负数
(2) 目标和为 0是要满足当前选择的路径上元素数为 k
(3) 每个元素仅能选择一次，必须向后选择（从大到小选择面对大数时可以有更好性能）
代码实现
func combinationSum3(k int, n int) [][]int {
ans := make([][]int,0)
perm := make([]int, 0)
var backtrack func(idx int, target int)
backtrack = func(idx int, target int) {
if target == 0 {
if len(perm) == k {
ans = append(ans, append([]int(nil), perm...))
}
return
}
if target < 0 {
return
}
for i:=9; i>= 1; i-- {
if i > idx {
continue
}
perm = append(perm, i)
backtrack(i-1,target-i)
perm = perm[:len(perm)-1]
}
}
backtrack(9, n)
return ans
}子集
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解空间树：所谓子集，即分为选择包含当前元素 和不包含当前元素两种情况。
可行解约束条件： 每一轮选择都应该到达可选列表的尾部，即使不选择元素。所以 idx =列表长度时为一个可行解。
剪枝约束 ：从解空间树可以看到没有剪枝情况。
代码实现：
func subsets(nums []int) [][]int {
ans := make([][]int, 0)
perm := make([]int, 0)
var backtrack func(idx int)
backtrack = func(idx int) {
if idx == len(nums) {
ans = append(ans, append([]int(nil), perm...))
return
}
perm = append(perm, nums[idx])
backtrack(idx + 1)
perm = perm[:len(perm)-1]
backtrack(idx + 1)
}
backtrack(0)
return ans
}子集 II
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
和上一题的区别在于增加了重复元素，对于重复元素类问题可以从上面全排列 II，组合 II 等多道题中发现统一的处理方式，就是 先对元素排序，再绑定式选择，即要选择重复元素前提是与它相同的前面的元素均被选择，代码实现也是统一的标记方法。
解空间树：
可行解约束条件：与上题一致，idx =列表长度时为一个可行解。
剪枝约束条件：不选择重复解，即要选择重复元素前提是与它重复的前面的元素均被选择
代码实现：
func subsetsWithDup(nums []int) [][]int {
ans := make([][]int, 0)
perm := make([]int, 0)
vis := make([]bool, len(nums))
var backtrack func(idx int)
backtrack = func(idx int) {
if idx == len(nums) {
ans = append(ans, append([]int(nil), perm...))
return
}
//这里要注意，剪枝约束作用域是在选择元素时进行剪枝，空选择情况下没有剪枝约束
if !(vis[idx] || (idx > 0 && nums[idx] == nums[idx-1] && !vis[idx-1])) {
perm = append(perm, nums[idx])
vis[idx] = true
backtrack(idx + 1)
vis[idx] = false
perm = perm[:len(perm)-1]
}
backtrack(idx + 1)
}
backtrack(0)
return ans
}字符排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]解空间树：这里使用了一个（abbc）字符串进行示例，其实和全排列 II 有重复元素数组的排列思路是一致的
可行解约束条件： 已选择路径长度等于元素总数
剪枝约束条件：不允许重复选择，模板式的去重方式，标记-判断
代码实现：
func permutation(s string) []string {
sb := []byte(s)
sort.Slice(sb, func(i, j int) bool {
return sb[i] < sb[j]
})
ans := make([]string, 0)
perm := make([]byte, 0)
vis := make([]bool, len(sb))
var backtrack func()
backtrack = func() {
if len(perm) == len(sb) {
ts := string(perm)
ans = append(ans, ts)
return
}
for i:=0; i<len(sb); i++ {
if vis[i] || i >0 && sb[i] == sb[i-1] && !vis[i-1] {
continue
}
perm = append(perm, sb[i])
vis[i] = true
backtrack()
vis[i] = false
perm = perm[:len(perm)-1]
}
}
backtrack()
return ans
}生成合法括号
设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为： "((()))", "(()())", "(())()", "()(())", "()()()"
解空间树
可行解约束条件： 所有括号（左右括号）都被选择
剪枝约束条件：（1）红色标记部分：左括号选择已达最大数量时不可以再选择左括号
（2）黑红色标记部分：当剩余左括号大于等于右括号时必须优先选择左括号
代码实现：
func generateParenthesis(n int) []string {
ans := make([]string, 0)
perm := make([]byte,0)
var backtrack func(lNum,rNum int)
backtrack = func(lNum,rNum int) {
if len(perm) == 2*n {
ans = append(ans, string(perm))
return
}
if lNum > 0 {
perm= append(perm, '(')
backtrack(lNum-1, rNum)
perm = perm[:len(perm)-1]
}
if rNum > lNum {
perm = append(perm,')')
backtrack(lNum, rNum-1)
perm = perm[:len(perm)-1]
}
}
backtrack(n,n)
return ans
}N皇后问题
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。本题的思路是先以行为纬度，选择当前行合适的位置放置一个皇后，然后再下一行的每一列上寻找可以满足放置皇后的位置。 所谓皇后之间不可以攻击，可以抽象为二维数组中不存在两个元素处于同行同列同对角线上，这里对角线指的是以当前元素为中心的正反斜线。根据这个思路我们可以简单的绘制下面的解空间树。
其中绿色节点，表示当前选择路径所有皇后可以满足条件放置。
深红色节点表示，当前选择与前面的选择在同一列上
黑红色节点表示，当前选择与前面的选择在同一正对角线（从左上到右下方向的斜线）上
粉红色节点表示， 当前选择与前面的选择在同一反对角线（从左下到右上方向的斜线）上
剪枝约束，从解空间树上的分析来看，不允许选择同一列同对角斜线上的位置。
不同列可以通过列 ID 进行判断，可以如何判断对角斜线上是否已经存在皇后呢？
从左上往右下方向斜线上的每个位置，满足行坐标与列坐标的差值是相同的
从左下往右上方向斜线上的每个位置，满足行坐标与列坐标的和值是相同的
上面两条结论读者可以自己画图计算理解，因此我们就可以通过使用行列坐标和，差唯一值进行标记元素所在斜线上皇后的存在情况。
代码实现如下：
func solveNQueens(n int) [][]string {
//全局变量用于记录结果
solutions := [][]string{}
//记录皇后所在位置，索引代表行号，值代表皇后所在列号
queues := make([]int, n)
for i:=0; i<n; i++ {
queues[i] = -1
}
//用于记录哪些列已经有皇后存在
columns := map[int]bool{}
//用于记录哪些对角位置有皇后存在
diagonals1, diagonals2 := map[int]bool{}, map[int]bool{}
//用于将整数数组结果转换成棋盘表达式
var generateBoard func()[]string
generateBoard = func()[]string {
board := []string{}
for i:=0; i<n; i++ {
row := make([]byte,n)
for j :=0; j<n; j++ {
row[j] = '.'
}
//第 i 行 queues[i]列上放置了皇后
row[queues[i]] = 'Q'
board= append(board, string(row))
}
return board
}
var backtrack func(row int)
backtrack = func(row int) {
//可行解条件。所以皇后全部放置
if row == n {
board := generateBoard()
solutions = append(solutions, board)
}
//按列尝试放置
for i:=0; i<n; i++ {
//同列位置已经存在皇后
if columns[i] {
continue
}
//左上到右下方向，元素坐标行-列值相同
diagonal1 := row - i
if diagonals1[diagonal1] {
continue
}
//左下到右上方向，元素坐标行+列值相同
diagonal2 := row + i
if diagonals2[diagonal2] {
continue
}
//满足条件进行选择
queues[row] = i
//标记列
columns[i] = true
//标记斜线方向
diagonals1[diagonal1],diagonals2[diagonal2] = true, true
//下一行选择
backtrack(row+1)
//撤销本次选择，撤销标记
queues[row] = -1
delete(columns, i)
delete(diagonals1, diagonal1)
delete(diagonals2, diagonal2)
}
}
backtrack(0)
return solutions
}三、 总结
回溯法又被称为万能算法，因为其简单易用性，但在算法的选择过程中需要多种因素综合，当遇到排列选择组合等问题时优先选择回溯法解题，在解决过程中要时刻考虑性能问题，因为回溯法在解空间树剪枝条件不充足情况下性能会大幅下降。
根据前面的题目也能看出，使用回溯法是有规矩可寻的。解题步骤明确，代码模板清晰。只需要遵循具体步骤和代码模板填充相关条件即可。
解题步骤
设计正确的解空间树、分析剪枝约束条件、分析可行解约束条件
代码模板
//1. 定义全局变量用于记录结果
ans := make([][]int,0)
perm := make([]int, 0)
//2. 定义递归方法
backtrack := func() {
if 可行解约束 {
ans = append(ans,...)
}
if 剪枝约束{
return
}
for xxx {
//选择
perm = append(perm, ...)
//递归
backtrac()
//回溯，撤销选择
perm = perm(:len(perm)-1)
}
} 原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。