其他
面试高频算法题之回溯算法（全文六千字）
大家好，我是程序员学长~
今天给大家带来一篇面试高频算法题之回溯算法的详细解析，全文包含6道大厂笔试面试算法真题，一举拿下回溯算法这个知识点，让算法不在成为进入大厂的绊脚石。
如果喜欢，记得点个关注哟~
回溯算法
全文概览
回溯算法基础知识
回溯算法的基本思想
回溯算法和贪心算法的区别
回溯算法模板
路径：表示已经做出的选择。 选择列表：表示当前可以做的选择。 结束条件：也就是到达多叉树的叶子节点，即⽆法再做选择。
代码框架如下所示：
result=[]
def backtrack(路径, 选择列表):
if 满⾜结束条件:
result.append(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
组合总和
39. 组合总和
问题描述
示例：
输入：candidates = [2,3,6,7]，target = 7
输出：[[2,2,3]，[7]]
分析问题
还记得回溯算法的模板吗？如下所示。
result=[]
def backtrack(路径, 选择列表):
if 满⾜结束条件:
result.append(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其中
路径：指从 candidates 选择出的元素。 选择列表：指给定的候选集合 candidates 。 结束条件：指路径列表中元素和是否等于目标值target，为了方便处理，我们可以定义一个变量 sum 表示路径中的元素和。
代码如下所示。
class Solution:
def combinationSum(self, candidates, target):
result = []
def backtrack(start, sum, path,candidates):
#如果路径和大于target，直接返回
if sum>target:
return
#如果路径和等于target,将该路径加入到结果列表中
if sum==target:
result.append(path[:])
return
for i in range(start, len(candidates)):
#添加元素到path（做选择）
path.append(candidates[i])
#递归查找
backtrack(i, sum + candidates[i], path, candidates)
#移除添加的元素（撤销选择）
path.pop()
backtrack(0,0,[],candidates)
return result
通过剪枝进行优化处理
class Solution:
def combinationSum(self, candidates, target):
result = []
def backtrack(start, sum, path,candidates):
#如果路径和等于target,将该路径加入到结果列表中
if sum==target:
result.append(path[:])
return
for i in range(start, len(candidates)):
#剪枝处理
if sum + candidates[i] > target:
break
#添加元素到path
path.append(candidates[i])
backtrack(i, sum + candidates[i], path, candidates)
#移除添加的元素
path.pop()
#排序处理
candidates.sort()
backtrack(0,0,[],candidates)
return result
加起来和为目标值的组合
40. 组合总和 II
问题描述
注意：
题目中所有的数字（包括目标数 t ）都是正整数。 组合中的数字 ( a1, a2, … ak) 要按非递减排序 ( a1 < = a2 <=, … <=ak )。 结果中不能包含重复的组合。 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。
示例：
输入：candidates=[1,2,3]，target=3
输出：[[1,2], [3]]
分析问题
为了避免生成的组合重复，如果在同一级递归中，遇到两个相同的数，我们应该只递归搜索靠前的那一个。
因为已经对原数组进行排序了，然后在递归的过程中，如果当前i对应的值比target大，那么就可以说明i之后的值都比target大，所有就不需要继续搜索，可以直接结束递归了。
我们以 candidates=[1,2,3]，target=3 来看一下递归调用树。
下面我们来看一下代码的实现。
class Solution(object):
def combinationSum2(self, candidates, target):
n=len(candidates)
res=[]
if n==0:
return res
# 对原数组进行排序
sort_candidates = sorted(candidates)
def dfs(i,target,tmp):
#如果为0，添加到结果中
if target==0:
res.append(tmp[:])
return
for j in range(i,n):
#如果当前元素比target大，那就进行剪枝处理
if sort_candidates[j] > target:
break
if j > i and sort_candidates[j] == sort_candidates[j - 1]:
#剪枝、避免重复
#因为前面那个同样的数已经经历过dfs，再拿同样的数dfs就会得到重复的答案
continue
#将元素sort_candidates[j]加入组合中
tmp.append(sort_candidates[j])
#递归搜索下一个元素
dfs(j+1,target-sort_candidates[j],tmp)
#回溯操作
tmp.remove(sort_candidates[j])
#从0开始搜索
dfs(0,target,[])
return res
没有重复项数字的所有排列
46. 全排列
问题描述
示例：
输入：[1，2，3]
输出：[[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1]]
分析问题
Tips:是不是很熟悉，是的，就是我们初高中学的知识。
当start==n时，表示n个位置都已经填完，找到了一种排列，我们将result放到最终的结果数组中，递归结束。
当start < n时，我们需要从剩下的数中（0到start-1位置没有使用的数）选择一个填入start位置。所以这里我们需要引入一个标记数组visited来标记一下已经填过的数，在填第start位置时，我们选择一个未被标记过的数将其填入，然后将其进行标记，然后再继续填下一个位置，即调用函数 backtrack(first + 1, result)。
我们以 [1, 2, 3] 为例，来看一下递归调用树。
下面我们来看一下代码实现。
class Solution:
def permute(self, nums):
def backtrack(start,tmp):
# 所有数都填完了
if start == n:
res.append(tmp[:])
return
#在1，n中寻找一个数填入start位置
for i in range(0, n):
if not visited[i]:
#继续递归填下一个数
tmp.append(nums[i])
visited[i]=True
backtrack(start + 1,tmp)
#回溯
tmp.pop()
visited[i] = False
n = len(nums)
#最终的结果
res = []
#用来标记是否遍历过
visited=[False]*n
print(visited)
backtrack(0,[])
return res
有重复项数字的所有排列
47. 全排列 II
问题描述
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例：
输入：[1，1，2]
输出：[[1，1，2]，[1，2，1]，[2，1，1]]
分析问题
如下所示，我们以序列**[1, 2, 2]**为例。
if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
continue
下面我们来看一下代码实现。
class Solution:
def permute(self, nums):
def backtrack(start,tmp):
#所有数都填完了
if start == n:
res.append(tmp[:])
return
#在1，n中寻找一个数填入start位置
for i in range(0, n):
#如果没有使用过
if visited[i]:
continue
#如果nums[i]不是第一个未被填过的数字，进行剪枝处理
if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
continue
#放入序列中
tmp.append(nums[i])
visited[i]=True
#继续递归填下一个数
backtrack(start + 1,tmp)
#回溯
tmp.pop()
visited[i] = False
n = len(nums)
#最终的结果
res = []
#用来标记是否遍历过
visited=[False]*n
print(visited)
backtrack(0,[])
return res
字符串全排列
剑指 Offer 38. 字符串的排列
问题描述
示例：
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
分析问题
下面我们来看下代码实现。
class Solution:
def permutation(self, s):
#字符串转换成list
c = list(s)
#存放结果
res = []
def dfs(x):
#如果已经到最后一位，添加排列方案到结果中
if x == len(c) - 1:
res.append(''.join(c))
return
#定义一个set，记录该位置上出现过的字符
dic = set()
#
for i in range(x, len(c)):
#该位置已经出现过这个字符，避免重复，直接跳过
if c[i] in dic:
continue
#该字符添加到set中
dic.add(c[i])
#将字符c[i]固定在第x位上
c[i], c[x] = c[x], c[i]
#接着固定第x+1位的字符
dfs(x + 1)
#恢复交换
c[i], c[x] = c[x], c[i]
#从第0位开始
dfs(0)
return res
N皇后
51. N 皇后
问题描述
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：4 皇后问题存在两种不同的解法
分析问题
代码如下所示：
class Solution(object):
def solveNQueens(self, n):
def add_element(row,col):
queens.add((row,col))
cols[col] = 1
d_diagonals[row + col] = 1
m_diagonals[col - row] = 1
def remove_elemet(row,col):
queens.remove((row,col))
cols[col] = 0
d_diagonals[row + col] = 0
m_diagonals[col - row] = 0
def add_to_list():
solution = []
for _, col in sorted(queens):
solution.append("."*col + "Q" + "."*(n-col-1))
output.append(solution)
def check(row, col):
return not (cols[col] + d_diagonals[row+col] + m_diagonals[col-row])
def backtrack(row=0):
for i in range(n):
if check(row, i):
add_element(row, i)
if row + 1 == n:
add_to_list()
else:
backtrack(row + 1)
remove_elemet(row, i)
cols = [0] * n
# 对角线元素
m_diagonals = [0] * (2 * n - 1)
d_diagonals = [0] * (2 * n - 1)
queens = set()
output = []
backtrack()
return output
原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！
欢迎关注公众号 程序员学长，助你少走弯路进大厂。
你知道的越多，你的思维越开阔。我们下期再见。