网站Logo 栖息地
首页
数据结构与算法
瞬间
关于

回溯法

calmjelly
4
2026-02-10

2016年读研一，初次学习数据结构与算法，被回溯法给卡住了。

2021年面试小红书，面试官要手写八皇后，G了。其实这个题目我以前刷过，也知道思路，也许是没有真正理解吧，临场在没有任何提示的面试平台上没有写出来。

在AI横行的时代重新学这个东东感觉有点不合群，不过我认为数据结构与算法还是很值得学习的，毕竟就算AI帮我写完了代码我还是要审查AI写的代码可靠性如何。从码农变成了审校，那么还是应该具备审查代码好坏的能力。

其实是公司最近大裁员，真有点虚了，感觉未来1~2年大概率要提桶了。

第一遍刷leetcode时候用的java，这次用python吧。

回溯法到底是什么

简单理解：选一条路，走到底（得到解或者发现是死路），撤销刚才的选择，换一条路继续，直到试完所有的可能性。

涉及回溯法的题目基本都长这个样子：

res = []
path = []

def backtrack(choices_or_index):
    # 1) 终止条件：收集结果 or 返回
    if 满足条件:
        res.append(path.copy()) 
        return

    # 2) 遍历选择
    for choice in 可选项:
        # 3) 做选择
        path.append(choice)

        # 4) 递归深入
        backtrack(下一层参数)

        # 5) 撤销选择（回溯）
        path.pop()

backtrack(初始参数)
return res

常见题型

子集/组合：用start控制，不回头

  • 子集：每个元素选 / 不选

  • 组合：从 n 个里选 k 个

  • 组合总和：去凑一个 target

核心参数：start（下一次从哪里开始选，避免重复选择同一元素）

特征：顺序无关

例题：子集

https://leetcode.cn/problems/subsets/description/?envType=problem-list-v2&envId=backtracking

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtrack(start):
            res.append(path[:])

            for i in range(start , len(nums)):
                path.append(nums[i])
                backtrack(i+1)
                path.pop()
        
        backtrack(0)
        return res

为什么这样能去重？

因为start 把“下一步能选的范围”限制为“只能往后”，让每个集合只能按一种顺序生成，因此不会因为顺序不同而重复。

  • start 表示：下一步只能从哪些位置开始选

  • backtrack(i+1) 表示：选了 i 之后，后面只能选更大的下标

例题：组合

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res:List[List[int]] = []
        path:List[int] = []

        def backtrack(start:int) -> None:
            if len(path) == k:
                res.append(path.copy())
                return
            
            need = k - len(path)
            max_i = n - need + 1

            for i in range(start, max_i + 1):
                path.append(i)
                backtrack(i+1)
                path.pop()
        
        backtrack(1)
        return res

排列：用used/visited控制每个元素只访问一次

特征：顺序会影响结果，元素一样，顺序不同也是不同的解。

例题：全排列

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

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res:List[List[int]] = []
        path:List[int] = []
        used = [False] * len(nums)

        def dfs() -> None:
            if len(path) == len(nums):
                res.append(path.copy())
                return
            
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])

                dfs()

                path.pop()
                used[i] = False
        
        dfs()
        return res

排列的顺序很重要，这里就不需要用start来限制下一次路线选择时候的取值了。

切分 / 拆分

典型特征：枚举“切口”

在一段连续序列上，枚举下一刀切在哪里，把前面切出来的这一段当作一个块，递归去切剩下的部分。

如果题目是：

  • 对字符串/数组做 “分割 / 切分 / 拆分 / 插入分隔符 / 还原”

  • 输出所有方案（或找一个方案）

此时如果能枚举下一段的结束下标，那大概率就是切口枚举。

例如：复原IP地址，分割回文串等。

例题：复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        res = []
        path = []

        # 无解判断
        if n < 4 or n > 12:
            return res
        
        def is_valid(seg:str) ->bool:
            if len(seg) > 1 and seg[0] =='0':
                return False
            return 0 <= int(seg) <=255
        

        def backtrack(start:int) ->None:
            remaining_segs = 4 - len(path)
            remaining_chars = n - start
            if remaining_chars < remaining_segs or remaining_chars > remaining_segs * 3:
                return
            if len(path) == 4:
                if start == n:
                    res.append(".".join(path))
                return

            for end in range(start , min(start+3,n)):
                seg = s[start:end+1]
                if not is_valid(seg):
                    continue
                path.append(seg)
                backtrack(end+1)
                path.pop()
        backtrack(0)
        return res

棋盘/网格搜索

典型特征：方向数组+visited

有点像在图里面DFS，遇到边界或者visited时候回溯。

例题：N皇后

几个关键：

  1. 按行放置，一行放一个皇后，同一行冲突就直接避免了

  2. 在每一层递归中，需要逐个尝试皇后应该当前行的哪一列

  3. 记录冲突：列冲突/主对角线冲突/副对角线冲突。

对角线冲突可以这样快速判断：

  1. 列冲突：用一个cols set判断，已存在的不能再放

  2. 主对角线冲突：同一条主对角线上的格子，他们row-col的值是相同的

  3. 副对角线冲突：同一条副对角线上的格子，他们row-col的值是相同的

左上角(0,0),右下角(n,n)，特点是从左向右递增、从上往下递增，那么主对角线上，每次行列都+1，所以差值不变。

副对角线上，一个+1一个-1，所以和值不变。用这个特点来做过滤。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res:List[List[str]] = []
        path = [-1] * n
        
        cols = set()
        diag1 = set()
        diag2 = set()

        def build_board()->List[str]:
            board = []
            for r in range(n):
                row = ['.']*n
                row[path[r]]='Q'
                board.append(''.join(row))
            return board
        
        def backtrack(row:int)->None:
            if row ==n:
                res.append(build_board())
                return
            for col in range(n):
                d1 = row - col
                d2 = row + col
                if col in cols or d1 in diag1 or d2 in diag2:
                    continue
                
                path[row] = col
                cols.add(col)
                diag1.add(d1)
                diag2.add(d2)

                backtrack(row + 1)

                cols.remove(col)
                diag1.remove(d1)
                diag2.remove(d2)
                path[row] = -1

        backtrack(0)
        return res

动物装饰