回溯算法

参考：https://zhuanlan.zhihu.com/p/93530380

概念理解

概念

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

用回溯法解题的一般步骤：

针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

确定结点的扩展搜索规则

以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

解决一个回溯问题，实际上就是一个决策树的遍历过程。只需要思考 3 个问题：

路径：也就是已经做出的选择。

选择列表：也就是你当前可以做的选择。

结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法的框架：


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

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

# 路径：用来记录走过的选择
# 选择列表 ：表示当前可以做出的选择result = []

例题

LC78: 子集

问题：给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

分析: 子集长度包含len(nums)+1种，即长度为0、为1、为2，....，为len(nums)，所以有如下框架。


def functions(nums):
    result = []
    result.append([])
    for i in range(1, len(nums)+1):
        backtrack(nums=nums, result=result, length=i, index=0, sub=[])
    return result

程序调用次回溯算法，每次生成的子集长度为，。

回溯算法如下：

每个节点的子节点为当前位置所存在的可能选择，即选择列表。以生成长度为2的子集为例，执行过程如下

由回溯算法框架得到以下完整算法：


def backtrack(nums, result, length, index, sub):
    # 满足条件则添加到结果中。注：此处添加需要深拷贝
    if len(sub) == length:
        result.append(sub[:])
				return
    # 遍历选择路径
    for i in range(index, len(nums)):
        sub.append(nums[i]) # 做选择
        backtrack(nums, result, length, i+1,sub) # 因为每次的选择都是当前值之后的
        sub.pop() # 撤销选择

当然，本题开始便说明了是所有子集，所以不需要判断是否满足条件，直接加到res中即可


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.dfs(path=[], choice=nums, index=0) 
        return self.res

    def dfs(self, path, choice, index):
# path 为路径
# choice , index 共同为选择列表
        self.res.append(path[:])
        for i in range(index, len(choice)):
            path.append(choice[i])
            self.dfs(path, choice, i+1)
            path.pop()

LC46: 全排列

问题：给定一个没有重复数字的序列，返回其所有可能的全排列

分析：n 个不重复的数，全排列共有 n! 个

先绘制如下回溯树，每个节点的子节点均为当前节点的选择列表

通过一个hashlist来记录是否走过某值


def permute(self, nums: List[int]) -> List[List[int]]:
    result = []
    visited = {}
    for num in nums:
        visited[num] = False
    self.backtrack(nums, result, visited, [])
    return result

def backtrack(self, nums, result, visited, ls):
    if len(ls) == len(nums):
        result.append(ls[:])
        return
    for num in nums:
        if not visited[num]:
            ls.append(num)
            visited[num] = True
            self.backtrack(nums, result, visited, ls)
            ls.pop()
            visited[num] = False

代码中，ls是路径，visited辅助nums得到选择列表,其实可以不用visited辅助，直接判断num in ls就也可以得到路径，代码如下：


# 改进版
def permute(self, nums: List[int]) -> List[List[int]]:
    result = []
    self.backtrack(nums, result, [])
    return result

def backtrack(self, nums, result, ls):
    if len(ls) == len(nums):
        result.append(ls[:])
        return
    for num in nums:
        if num not in ls:
            ls.append(num)
            self.backtrack(nums, result, ls)
            ls.pop()

'''
ls为路径
nums 和 ls 共同得到选择列表
'''

总结

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：


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

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

# 路径：用来记录走过的选择
# 选择列表 ：表示当前可以做出的选择

写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。