面试高频算法题之回溯算法（全文六千字）

大家好，我是程序员学长~

今天给大家带来一篇面试高频算法题之回溯算法的详细解析，全文包含6道大厂笔试面试算法真题，一举拿下回溯算法这个知识点，让算法不在成为进入大厂的绊脚石。

如果喜欢，记得点个关注哟~

本文有点长，在公众号浏览可能不方便，我已将本文制作成带目录的PDF版本，获取本文PDF版本，请扫下方二维码加我微信，备注算法。

回溯算法

全文概览

回溯算法基础知识

回溯算法的基本思想

回溯算法本质上就是一个枚举的过程。在枚举搜索的过程中尝试寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径；或者当寻找到问题的解后，将其加入结果中，然后“回溯”返回，尝试还有没有其他满足条件的解。

为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

回溯算法和贪心算法的区别

贪心算法只能根据当前的状态，选择最优的走法，走向下一步，就和人的一生一样，只能在岔路口选择一条当前条件下最优的路走，过去就过去了，不能回退，只能一条路走到黑。而回溯算法，可以有重来的机会，比如选择了一条路，发现这条路不适合自己，然后回退到岔路口，重新来选择。这就是回溯的思想（类似于可以穿越一样）。

回溯算法模板

求解回溯算法的相关问题，实际上就是一个多叉树的遍历过程。在给出回溯算法模板之前，我们先来看几个概念。

• 路径：表示已经做出的选择。
• 选择列表：表示当前可以做的选择。
• 结束条件：也就是到达多叉树的叶子节点，即⽆法再做选择。

代码框架如下所示：

result=[]
def backtrack(路径, 选择列表):
    if 满⾜结束条件:
        result.append(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择 

代码框架中最核心的部分就是 for循环中的递归，在递归调⽤之前「做选择」，在递归调⽤之后「撤销选择」，即“回退”。

组合总和

39. 组合总和

问题描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同的组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

输入：candidates = [2,3,6,7]，target = 7

输出：[[2,2,3]，[7]]

解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。

分析问题

这道题我们可以采用回溯算法来求解，即列出所有可能的组合，然后在这些组合中筛选出满足条件的序列。

还记得回溯算法的模板吗？如下所示。

result=[]
def backtrack(路径, 选择列表):
    if 满⾜结束条件:
        result.append(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择 

其中

• 路径：指从 candidates 选择出的元素。
• 选择列表：指给定的候选集合 candidates 。
• 结束条件：指路径列表中元素和是否等于目标值target，为了方便处理，我们可以定义一个变量 sum 表示路径中的元素和。

这里需要注意一点，对于求解组合相关的问题，我们需要一个变量start来表示 for 循序的起始位置，即从选择列表的哪个位置开始遍历。

代码如下所示。

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

通过剪枝进行优化处理

通过分析上述给出的代码，如果 sum 加上一个数已经大于目标值 target，那么 sum 加一个更大的数肯定也是大于 target 的。基于这个想法，我们可以对上述代码进行优化处理，具体代码如下所示。

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

问题描述

给出一组候选数 c 和一个目标数 t ，找出候选数中加起来和等于 t 的所有组合。c 中的每个数字在一个组合中只能使用一次。

注意：

1. 题目中所有的数字（包括目标数 t ）都是正整数。
2. 组合中的数字 ( a₁, a₂, … a_k) 要按非递减排序 ( a₁ < = a₂ <=, … <=a_k )。
3. 结果中不能包含重复的组合。
4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

示例：

输入：candidates=[1,2,3]，target=3

输出：[[1,2], [3]]

分析问题

这道题其实是搜索问题，对于搜索问题，我们最先想到的应该是“回溯法”，列举出所有可能的组合，然后在这些组合中筛选出满足条件的组合。而题目要求组合中的数字按非递减顺序排序，所以我们首先对原数组进行排序，这样在通过回溯法求解满足条件的组合时，就能保证组合中的元素是非递减的。

回溯算法一般都是通过递归来实现的，首先我们定义一个递归函数 dfs(i, target，cur)，其中i表示搜索到了数组中的哪个位置了，target表示目前距离目标值还差多少，cur表示当前的组合。这里有两点需要注意。

1. 为了避免生成的组合重复，如果在同一级递归中，遇到两个相同的数，我们应该只递归搜索靠前的那一个。

2. 因为已经对原数组进行排序了，然后在递归的过程中，如果当前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. 全排列

问题描述

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例：

输入：[1，2，3]

输出：[[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1]]

分析问题

由于题目要求是求数组nums的全排列，所以我们可以很直观的想到采用回溯算法来求解，回溯算法的本质就是列举出所有的可能结果，然后在这些结果中筛选出满足条件的。

Tips:从n个不同的元素里每次取一个，一共取n次，按照取出的顺序排成一排，形成一个排列。那么所有的排列情况就叫做全排列。

这个问题可以看做是有n个盒子排成一排，然后需要从袋子中取出n个球，每次不放回的取一个填入盒子中，有多少种填法。

Tips:是不是很熟悉，是的，就是我们初高中学的知识。

我们可以使用回溯法来求解，即我们对每个盒子依次尝试填入一个数，直到盒子全部填完，就得到了一种排列。

回溯算法一般都是通过递归来实现的，首先我们定义一个递归函数 backtrack(start，result)，其实start表示从左到右填到序列的哪个位置了，result表示当前序列的结果。

1. 当start==n时，表示n个位置都已经填完，找到了一种排列，我们将result放到最终的结果数组中，递归结束。

2. 当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]]

分析问题

这道题是上一题的升级版本，其中给定的序列nums中有重复数字，那么我们该如何求出所有可能的全排列呢？如果采取上一题这种方法求解，就会出现很多重复的情况，因为对于第 x 的位置，如果存在重复的数字 i，我们每次会将重复的数字都重新填上去并继续尝试，这样就会导致最后答案的重复，因此我们需要处理这个情况。

如下所示，我们以序列**[1, 2, 2]**为例。

那我们在遍历的过程中如何进行剪枝操作呢？要解决重复问题，我们只需要保证在填入第x位置的时候，重复数字只能被填入一次。对于解决重复问题，这里有一个小技巧，如果列表中有重复的元素，那我们如何快速找到重复元素呢，最简单的方式就是先对列表进行排序，将重复的元素放在一起，这样我们只需要比较附近的元素就能判断是否重复。

下面我们来看一下如何进行剪枝操作，我们首先对序列进行排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在的重复集合中「从左往右第一个未被填过的数字」，即通过如下的判断条件进行剪枝：

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. 字符串的排列

问题描述

输入一个长度为n字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

示例：

输入：s = "abc"

输出：["abc","acb","bac","bca","cab","cba"]

分析问题

我们知道，对于一个长度为n的字符串（假设字符串中的字符都不相同），它的全排列方案共有n!种。

对于字符串的第一个字符，我们有n种选择，即从n个字符中选择1个放在字符串的首位，然后对于字符串的第二个字符，我们有n-1中选择，即除去放在首位的那个元素外后，从剩余的n-1个字符中选择1个放在字符串的第二位...，依次类推，所以生成的全排列方案有n*(n-1)*(n-2)...*1=n!种。

如果字符串中含有重复的字符，就会有重复的情况出现。为了排除重复方案，在固定某一位时，我们需要确保“每种字符只能在该位置出现一次”，比如对于字符串"aab"来说，在固定第一位时，我们只有两种方案，因为字符串中"aab"中出现了2个a，为了避免重复，我们只能让字符“a”出现一次。我们可以使用一个Set集合来记录这一位出现过的字符，如果已经出现过，我们就直接跳过就好了。

下面我们来看下代码实现。

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 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

输入：n = 4

输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解释：4 皇后问题存在两种不同的解法

分析问题

这道题我们可以使用回溯法来求解。具体来说，我们可以这么来考虑，我们把这个问题划分成N个阶段，然后将N个皇后分别放到第一行、第二行...直到最后一行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置皇后；如果不满足，那就再换一种放置的方法，然后再继续尝试。

为了判断一个位置所在的列和两个方向上的对角线是否已经有皇后存在，这里我们使用三个集合 cols，m_diagonals，d_diagonals 来分别记录每一列以及两个方向对角线是否有皇后。

因为棋盘上列的范围是 0~N-1，我们可以用集合 cols 对应的下标 0~N-1来表示每一列是否有皇后存在，如果第0列有皇后存在，则cols[0]=1，否则 cols[0]=0 。

下面我们来看一下如何用集合 m_diagonals，d_diagonals 来表示两个方向的对角线上是否有皇后存在。首先，我们来看一下两个方向上对角线上的每个位置的行列下标之间的关系。

对于从左上到右下方向的对角线来说，同一条斜线上的每个位置满足行下标与列下标之差相等，因此使用行下标与列下标之差即可明确表示每一条该方向的对角线。

对于从右上到左下方向的对角线来说，同一条斜线上的每个位置满足行下标与列下标之和相等，因此使用行下标与列下标之和即可明确表示每一条该方向的对角线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

代码如下所示：

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

原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！ 

欢迎关注公众号 程序员学长，助你少走弯路进大厂。 

你知道的越多，你的思维越开阔。我们下期再见。