回溯法定义

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

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

回溯是递归的副产品，只要有递归就会有回溯。深度优先搜索一般都用到了回溯法思想。所有回溯法解决的问题都可以抽象为树结构。

回溯法的设计思路

• 定义全局变量： 保存结果
• 参数设计：

候选列表：用来实现解空间舒节点的扩展

路径：用来记录当前节点的列表选择状态

条件变量：用来结束回溯的判断条件，以及用来剪枝的判断条件

全局变量：用来存储每个过程的解

• 回溯实现： 回溯的代码可以主要分为三部分

1. 回溯出口：找到满足约束条件下的解，记录该解，然后返回。一般放在函数的入口处；
2. 剪枝：剪枝的操作是为了减去解空间中不合适的分支。剪枝可以在回溯的出口处检测，也可以在节点扩展的时候检测；
3. 节点扩展：从候选列表中，选择合适的元素进行递归求解，在节点扩展阶段，需要改变路径和条件变量来适应新的节点。扩展的规则主要有排列和组合两种：

• 排列情况，要求每次选择没有选过的元素
• 组合情况，每次只能往后选，不能向前选，从后往前选就会出现重复问题
• 选择子串。这种情况下不同于排列和组合，现在这种情况将会选择一个连续的序列，属于组合情况的一种特列。

回溯法的应用

通常利用回溯法解决的问题：

• 组合问题：N个数中按一定规则找出k个数的集合
• 切割问题：一个字符串按照一定规则有几种切割方法
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后、解数独

组合问题和切割问题都是收集树的叶子节点；子集问题是收集树的所有问题全排列问题可以使用辅助列表保存访问过的index。

回溯法代码模板

result = []
def _backtrace(选择列表nums, 路径pre_list):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做检查
        做选择
        _backtrace(剩余选择列表, 路径)
        撤销选择

代码示例

• 全排列，给定一个没有重复数字的序列 [1,2,3,4]，返回其所有可能的全排列

# 算法一
def permute2(nums: List, solution: List = [], res: List = []):
    # nums.sort()  # 含有重复数字时进行排序
    if not nums:  # 边界条件, 出口
        res.append(solution)
        return  # 返回

    for i in range(len(nums)):
        # 遍历会进行到底，当出现不符条件返回上一步接着遍历,如不符合再返回一步... #
        # if i > 0 and nums[i] == nums[i - 1]: # 含有重复数字比较跳过遍历
        #     continue
        new_solution = solution + [nums[i]]  # 依次将nums里的数字放置排列组合的下一个位置上
        new_list = nums[0:i] + nums[i + 1:]  # new_list里是除了nums[i]以外的全部数字
        permute2(new_list, new_solution, res=res)  # 继续排列new_list里的数字
    return res

# 算法二
def permute(nums):
    if len(nums) == 0:
        return []
    res = []

    def _backtrace(nums, pre_list):
        """ 回溯 从待选列表中选取加入"""
        # 出口  已经选取完毕，记录结果
        if len(nums) <= 0:
            res.append(pre_list.copy()) 
            return
        else:
            for i in range(len(nums)):  
                # 1.做选择
                pre_list.append(nums[i])
                left_nums = nums.copy()
                left_nums.remove(nums[i])  # 没有重复元素，可以用remove从待选列表把该数删除
                # 2.递归
                _backtrace(left_nums, pre_list)
                # 3.撤销选择
                pre_list.pop()  # return之后 pop上个已遍历过的元素

    _backtrace(nums, [])
    return res

permute(nums) 方法的思路如下：

选择第一个位置上的数字，称之为 x；利用 permute(nums) 方法得到剩余数字的所有排列方式；把 x 放入这些数组的第一个位置。保存答案；回到第一步，改变 x； 尝试过所有x后输出答案。permute(nums) 方法的边界条件为，如果 nums 数组为空，那么将当前的排列方式加入结果集合并返回

• 棋盘N皇后算法；

def n_queens(n):
    # N皇后的约束条件：不能同行、不能同列、不能在同一个斜线上(45度 or 135度）
    # 参考https://www.92python.com/view/341.html
    
     # 检查盘面是否成立
    def check_board(row_index):
        for i in range(row_index):  # row_Index是当前行数
            if cols[i] == cols[row_index]:  # 检查竖线
                return False
            if abs(cols[i] - cols[row_index]) == row_index - i:  # 检查斜线
                return False
        return True

    # 布置第row_index行到最后一行的皇后
    def helper(row_index):
        if row_index == n:  # 边界条件
            board = [[0] * n] * n
            for i in range(n):
                board[i][cols[i]] = 1
            res.append(board)  # 把当前盘面加入结果列表
            return  # 返回
        for i in range(n):  # 依次尝试当前行的空格
            cols[row_index] = i
            if check_board(row_index):  # 检查当前盘面
                helper(row_index + 1)  # 进入下一行

    cols = [0] * n  # 每一行皇后的纵坐标
    res = []  # 结果列表
    helper(0)  # 从第1行开始
    return res

• 组合，从列表中选择n个不重复的数字组合

def combination(nums: List[int], n: int, index: int = 0, count: int = 0, 
                            rec: List[int] = [], res: List = []) -> List:
    """ num数字列表中选择n个不重复的数字组合
    :param nums: 列表
    :param n: 选择列表中N个数字组合
    :param index: 表示当前递归的位置
    :param count: 表示记录当前已经选了多少个数字
    :param rec: 列表记录中间递归过程中的结果
    :param res: 全局变量，存放最后组合结果
    :return:
    """
    if count == n:
        res.append(rec.copy())
        return

    for i in range(index, len(nums)):
        rec.append(nums[i])
        combination(nums, n, i + 1, count + 1, rec=rec, res=res)
        # 回溯, 尝试下一个数字
        rec.pop()
    return res

总结

回溯算法可以用一句话概括：不撞南墙不回头，一撞南墙就回头。整个过程就是在不断选择，不断重试，直到遍历结束！

#学习##python##日常分享#