🐍 Python 回溯算法教程（Backtracking）

🧠 什么是回溯算法？

回溯算法（Backtracking） 是一种通过尝试所有可能的选项来解决问题的算法思想。它通常用于解决组合、排列、子集等问题。

类比生活中的迷宫游戏：

  • 你走到一个岔路口，先选一条路走
  • 如果走不通，就“回退”回去试另一条路
  • 直到找到出口或尝试完所有路径为止

🔁 回溯算法的核心思想

  1. 选择一个选项（做出决策）
  2. 递归地继续探索下一步
  3. 如果发现当前路径不满足条件，就“撤销”之前的决策，回到上一步重新选择
  4. 直到找到所有可行解

📦 回溯算法的通用结构（模板）

def backtrack(参数):
    if 满足结束条件:
        把结果加入答案列表
        return
    for 所有可能的选择:
        做出选择
        backtrack(新的参数)
        撤销选择

🎯 常见回溯问题类型 & 模板示例

✅ 1. 组合问题（Combination）

题目描述：
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

🔢 示例：

输入：n = 4, k = 2
输出：

[
  [2,4],
  [3,4],
  [1,2],
  [1,3],
  [1,4]
]

🧩 模板代码：

def combine(n, k):
    res = []
    
    def backtrack(start, path):
        # 剪枝优化：剩下的数不够时提前终止
        if len(path) > k:
            return
        # 满足条件，记录结果
        if len(path) == k:
            res.append(path[:])
            return
        # 尝试每个数字
        for i in range(start, n + 1):
            path.append(i)                # 做出选择
            backtrack(i + 1, path)        # 进入下一层
            path.pop()                    # 撤销选择
    
    backtrack(1, [])
    return res

✅ 2. 全排列（Permutation）

题目描述：
给定一个没有重复数字的数组 nums，返回其所有全排列。

🔢 示例：

输入：nums = [1,2,3]
输出：

[
  [1,2,3], [1,3,2],
  [2,1,3], [2,3,1],
  [3,1,2], [3,2,1]
]

🧩 模板代码：

def permute(nums):
    res = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):     # 结束条件
            res.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True           # 标记使用
                path.append(nums[i])     # 做出选择
                backtrack(path)          # 进入下一层
                path.pop()               # 撤销选择
                used[i] = False          # 撤销标记

    backtrack([])
    return res

✅ 3. 子集问题（Subset）

题目描述：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

🔢 示例：

输入：nums = [1,2,3]
输出：

[
  [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]
]

🧩 模板代码：

def subsets(nums):
    res = []

    def backtrack(start, path):
        res.append(path[:])             # 每次都保存结果
        for i in range(start, len(nums)):
            path.append(nums[i])        # 做出选择
            backtrack(i + 1, path)      # 进入下一层
            path.pop()                  # 撤销选择

    backtrack(0, [])
    return res

✅ 4. N皇后问题（N-Queens）

题目描述：
在 N×N 的棋盘上放置 N 个皇后，使得它们不能互相攻击。

🧩 模板代码：

def solveNQueens(n):
    res = []

    def is_valid(row, col, cols):
        for r in range(row):
            if cols[r] == col:              # 同列冲突
                return False
            if abs(r - row) == abs(cols[r] - col):  # 对角线冲突
                return False
        return True

    def backtrack(row, cols):
        if row == n:
            board = []
            for r in range(n):
                line = ['.'] * n
                line[cols[r]] = 'Q'
                board.append("".join(line))
            res.append(board)
            return
        for col in range(n):
            if is_valid(row, col, cols):
                cols[row] = col         # 做出选择
                backtrack(row + 1, cols) # 进入下一层
                cols[row] = -1          # 撤销选择

    backtrack(0, [-1]*n)
    return res

🎨 可视化图解说明（伪代码风格）

backtrack():
│
├─→ 选择1 → backtrack() → ... → 满足条件？→ YES → 加入结果
│                   ↑
│                   └ NO → 继续尝试
│
├─→ 选择2 → backtrack()
│
└─→ ...

🧰 回溯算法小技巧总结

技巧 说明
🚫 剪枝优化 提前判断是否还有必要继续搜索，减少无效调用
🔄 参数设计 使用 start 避免重复，用 used 数组处理排列问题
🧹 路径清理 每次递归后记得 pop()，恢复现场
🧠 状态记录 用额外变量如 used、cols 来辅助判断合法性

🧪 练习建议

你可以试着挑战以下问题：

  • [ ] 组合总和（Combination Sum）
  • [ ] 单词搜索（Word Search）
  • [ ] 解数独（Sudoku Solver）
  • [ ] 括号生成（Generate Parentheses）

📚 推荐学习路线图

回溯入门 👉 组合 👉 排列 👉 子集 👉 N皇后 👉 综合练习

🙋‍♂️ 如何继续学习？

如果你希望我继续扩展以下内容，请告诉我：

  • 如何实现剪枝优化？
  • 如何识别什么时候适合用回溯？
  • 如何用类封装回溯函数？
  • 如何画出递归树帮助理解？

😊

📌 结语：
回溯算法是面试高频考点之一，掌握好这个套路，可以轻松应对一大类 DFS 类型题目。多写几道题，你就能体会到它的魅力啦！

需要配套练习题或进阶讲解也可以随时告诉我哦 😊

6 条评论

  • @ 2025-5-24 15:35:57
    已修改
    
回溯算法模板
def backtrack(参数):
    if 满足结束条件:
        把结果加入答案列表
        return
    for 所有可能的选择:
        if 选择合法:
            做出选择
            backtrack(新的参数)
            撤销选择

    • @ 2025-5-24 15:31:14
      已修改
      数的分解

描述

给出一个正整数a，要求分解成若干个正整数的乘积，即a=a1×a2×a3×...×an，并且1<a1≤a2≤a3≤...≤an，问这样分解的种类有多少。注意到a=a也是一种分解。

 

例如，8可以分解成8=2*2*2,8=2*4,8=8总共3种。

 

代码如下，完善划线处的代码：

def fun(x, y=2):

    if x == 1:

        global ans

               ①        

    for i in range(y, x+1):

        if         ②        :

            fun(x//i,i)

lst = [2, 8, 9, 20] #测试数据

for i in lst:

    ans = 0

            ③        

    print(ans)

程序运行结果如下：

1

3

2

      def fun(x, y=2):
    if x == 1:  # 如果x等于1，说明已经完成一种符合要求的分解
        global ans
        ans += 1  # 将方案数加1，因为找到了一种合法的分解方式
    for i in range(y, x + 1):
        if x % i == 0:  
          # 如果x能被i整除，说明i是x的一个因数，可以继续分解
            x = x // i
            fun(x , i)  
          # 递归调用fun函数，继续对x除以i后的结果进行分解，同时更新起始因数为i
            x = x * i
  
lst = [2, 8, 9, 20]  # 测试数据
for i in lst:
    ans = 0
    fun(i, 2)  # 对测试数据列表中的每个数调用fun函数开始分解
    print(ans)

'''
回溯算法模板
def backtrack(参数):
    if 满足结束条件:
        把结果加入答案列表
        return
    for 所有可能的选择:
        if 选择合法:
            做出选择
            backtrack(新的参数)
            撤销选择
'''

      • @ 2025-5-17 21:28:49

        回溯算法是一种通过构建所有可能的解决方案并逐一验证来解决问题的方法。它非常适合解决约束满足问题，如组合问题、排列问题、图搜索问题等。下面是一个详细的Python回溯算法教程，适合0基础的学习者。

        什么是回溯算法？

        回溯算法采用试错的思想，尝试分步地解决问题。如果当前步骤不满足条件，则撤销上一步（或几步），回到之前的某个状态，然后重新尝试其他可能。这个过程一直持续到找到一个解决方案或者所有的可能性都已尝试过为止。

        回溯算法的基本模板

        这里提供一个简单的回溯算法模板：

        def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return
    
    # 遍历所有选择
    for next_candidate in list_of_candidates:
        if is_valid(next_candidate):
            # 做选择
            place(next_candidate)
            # 继续下一个元素
            backtrack(next_candidate)
            # 撤销选择
            remove(next_candidate)

# 初始化
init_state()
backtrack(init_state)

        示例：解决N皇后问题

        N皇后问题是回溯法的一个经典应用，目标是在N×N棋盘上放置N个皇后，使得它们不能互相攻击。即在每一行、每一列和每一对角线上最多只能有一个皇后。

        以下是使用Python实现的N皇后问题解法：

        def solve_n_queens(n):
    def could_place(row, col):
        return not (cols[col] + hills[row - col] + dales[row + col])
    
    def place_queen(row, col):
        queens.add((row, col))
        cols[col] = 1
        hills[row - col] = 1
        dales[row + col] = 1
    
    def remove_queen(row, col):
        queens.remove((row, col))
        cols[col] = 0
        hills[row - col] = 0
        dales[row + col] = 0
    
    def add_solution():
        solution = []
        for _, col in sorted(queens):
            solution.append('.' * col + 'Q' + '.' * (n - col - 1))
        output.append(solution)
    
    def backtrack(row = 0):
        for col in range(n):
            if could_place(row, col):
                place_queen(row, col)
                if row + 1 == n:
                    add_solution()
                else:
                    backtrack(row + 1)
                remove_queen(row, col)
    
    cols = [0] * n
    hills = [0] * (2 * n - 1)  # "hill" diagonals
    dales = [0] * (2 * n - 1)  # "dale" diagonals
    queens = set()
    output = []
    backtrack()
    return output

# 调用函数
solutions = solve_n_queens(4)
for solution in solutions:
    print(solution)

        在这个例子中，我们首先定义了一些辅助函数来检查是否可以放置皇后，以及放置和移除皇后的操作。backtrack函数实现了递归回溯的核心逻辑。最后，我们调用solve_n_queens函数来解决问题，并打印出所有可能的解。

        希望这个教程能帮助你理解如何使用Python编写回溯算法！

        • @ 2025-5-17 21:25:33
          已修改

          基本结构（模板）

          模板1：标准回溯框架（无重复元素）

          
def backtrack(path, choices):
    if 满足结束条件:
        记录结果
        return
    for 选择 in 选择列表:
        做选择
        backtrack(新的路径, 新的选择列表)
        撤销选择

          模板2：带剪枝的回溯

          
def backtrack(start, path):
    if 满足条件:
        加入结果
        return
    for i in range(start, 可选范围):
        if 剪枝条件:
            continue
        做选择
        backtrack(i+1, path+[选择])
        撤销选择

          模板3：回溯 + 缓存（记忆化搜索） 适用于有大量重复计算的问题，可以使用 lru_cache 或字典缓存中间结果。

          
from functools import lru_cache

@lru_cache(maxsize=None)
def backtrack(状态参数):
    if base case:
        return 结果
    for 选择 in 所有可能:
        res = backtrack(新状态)
        合并结果
    return 最终结果
          • @ 2025-5-17 21:24:41

            Python 回溯算法教程（从零基础开始）

            一、什么是回溯算法？

            回溯算法（Backtracking） 是一种系统性地搜索所有可能解的算法。它通过尝试构建候选解，并在发现当前路径无法得到有效解时“回退”一步，继续探索其他可能性。

            回溯算法通常用于解决组合问题、排列问题、子集问题、分割问题等需要穷举的场景。

            二、适合初学者的回溯思想图解

            想象你在迷宫中寻找出口，每走到一个岔路口就选择一条路走下去。如果这条路走不通了，你就回到上一个岔路口，换另一条路再试。这就是回溯的核心思想：深度优先搜索 + 剪枝 + 回退

            三、回溯算法基本模板

            模板1：通用回溯结构

            def backtrack(参数):
    if 满足结束条件:
        记录结果
        return
    for 选择 in 所有可能的选择:
        if 剪枝条件不满足:
            做选择
            backtrack(新的参数)
            撤销选择

            模板2：组合问题模板（选或不选）

            def backtrack(start, path):
    if 当前path满足条件:
        res.append(path[:])
        return
    for i in range(start, n+1):
        path.append(i)
        backtrack(i+1, path)
        path.pop()

            模板3：排列问题模板

            def backtrack(path, used):
    if len(path) == n:
        res.append(path[:])
        return
    for i in range(n):
        if not used[i]:
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False

            模板4：分割问题模板（如字符串分割成回文串）

            def backtrack(start, path):
    if start == len(s):
        res.append(path[:])
        return
    for end in range(start+1, len(s)+1):
        if is_palindrome(s[start:end]):
            path.append(s[start:end])
            backtrack(end, path)
            path.pop()

            四、实战案例：整数分解为递增因子乘积

            题目描述：

            给定一个正整数 a，要求将其分解成若干个正整数的乘积：

            $$a = a_1 \times a_2 \times a_3 \times \cdots \times a_n $$

            其中 1<a1≤a2≤a3≤⋯≤an1 < a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n

            求这样的分解方案有多少种。

            注意：a=aa = a 也是一种合法分解（即只包含自己本身）。

            示例：

            输入：a = 8
            输出：3
            解释：

            • 8 = 2 × 2 × 2
            • 8 = 2 × 4
            • 8 = 8

            思路分析：

            我们使用回溯法来枚举所有可能的因子组合。我们从最小因子 2 开始尝试，每次只能选择 大于等于前一个因子 的值，以保证因子是递增的。

            完整代码实现：

            def factor_decompose(a):
    res = []  # 存储所有分解方式
    
    def backtrack(start, path, product):
        """
        start: 下一次可以选择的最小因子
        path: 当前已选择的因子列表
        product: 当前因子乘积
        """
        if product > a:
            return  # 超过目标值，剪枝
        if product == a:
            res.append(path[:])  # 找到一组有效分解
            return
        
        for i in range(start, a + 1):
            if product * i > a:
                break  # 提前剪枝，避免无效计算
            path.append(i)
            backtrack(i, path, product * i)  # 继续下一层递归
            path.pop()  # 回溯，撤销当前选择

    backtrack(2, [], 1)  # 从2开始分解，初始乘积为1
    return len(res), res  # 返回种类数和具体分解方案

# 测试
a = 8
count, ways = factor_decompose(a)
print(f"分解 {a} 共有 {count} 种方式，分别是：")
for way in ways:
    print(" × ".join(map(str, way)))

            输出结果：

            分解 8 共有 3 种方式，分别是：
2 × 2 × 2
2 × 4
8

            五、代码解析与注释

            def factor_decompose(a):
    res = []  # 存储所有合法分解方式

    def backtrack(start, path, product):
        """
        start: 当前可选的最小因子（确保递增）
        path: 已选因子组成的列表
        product: 当前乘积
        """
        if product > a:
            return  # 剪枝：超过目标值直接返回

        if product == a:
            res.append(path[:])  # 找到一个合法分解，保存副本
            return

        for i in range(start, a + 1):  # 枚举下一个因子
            if product * i > a:
                break  # 提前剪枝：乘积会超过目标值就不继续了
            path.append(i)  # 做选择
            backtrack(i, path, product * i)  # 进入下一层递归
            path.pop()  # 撤销选择，回溯

    backtrack(2, [], 1)  # 初始从2开始，乘积为1
    return len(res), res

            六、复杂度分析

            • 时间复杂度：最坏情况下是指数级，但由于我们做了剪枝（提前终止），效率较高。
            • 空间复杂度：取决于递归深度和存储结果的数量。

            七、扩展练习题建议

            你可以用类似的方法尝试以下题目：

            1. LeetCode 2764 - 将数组划分成递增序列
            2. LeetCode 131 - 分割回文串
            3. LeetCode 39 - 组合总和
            4. LeetCode 254 - 因子的组合

            八、总结

            内容 说明
            核心思想 DFS + 剪枝 + 回退
            常见应用场景 组合、排列、子集、分割、全排列等
            关键点 正确设计递归函数参数、合理剪枝、及时回溯
            技巧 多打印中间变量调试，画出递归树帮助理解

            如果你是0基础入门者，建议你先掌握以下知识点后再学习回溯：

            • 函数递归调用机制
            • 列表操作（append/pop）
            • 条件判断与循环控制
            • 基本的DFS概念

            如果你希望我为你生成更多类似的问题讲解、可视化动画、或者PPT教学资料，请告诉我！我可以为你定制不同风格的学习内容 📚💡

            • @ 2025-5-17 21:24:05

              Python回溯算法教程（0基础）

              1. 回溯算法基本概念

              回溯算法是一种通过尝试所有可能的路径来寻找问题解的方法。当探索到某一步时，如果发现当前选择无法得到有效解，就"回溯"到上一步，尝试其他选择。

              核心思想：

              • 递归枚举所有可能的选择
              • 在递归过程中记录路径
              • 遇到无效解时剪枝（提前终止）

              典型应用场景：

              • 组合问题（如子集、排列）
              • 分割问题（如字符串分割）
              • 棋盘问题（如N皇后）
              • 路径问题（如迷宫寻路）

              2. 回溯算法的通用模板

              模板一：组合问题（无重复元素）

              def backtrack(start, path, res, nums):
    # 收集结果（根据具体问题调整）
    res.append(path[:])  # 保存当前路径
    # 遍历选择列表
    for i in range(start, len(nums)):
        # 做选择
        path.append(nums[i])
        # 递归（下一层决策）
        backtrack(i + 1, path, res, nums)  # i+1避免重复选择
        # 撤销选择
        path.pop()

# 示例调用
nums = [1, 2, 3]
res = []
backtrack(0, [], res, nums)
print(res)  # 输出所有子集：[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

              模板二：排列问题（有重复元素）

              def backtrack(path, used, res, nums):
    # 终止条件：路径长度等于原数组长度
    if len(path) == len(nums):
        res.append(path[:])
        return
    # 遍历选择列表
    for i in range(len(nums)):
        # 剪枝：跳过已使用的元素或重复元素
        if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
            continue
        # 做选择
        used[i] = True
        path.append(nums[i])
        # 递归
        backtrack(path, used, res, nums)
        # 撤销选择
        used[i] = False
        path.pop()

# 示例调用
nums = [1, 1, 2]
nums.sort()  # 先排序，便于处理重复元素
used = [False] * len(nums)
res = []
backtrack([], used, res, nums)
print(res)  # 输出所有排列：[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

              3. 正整数分解问题分析

              问题描述：
              给定正整数a，将其分解为若干个正整数的乘积a = a1×a2×...×an，要求1 < a1 ≤ a2 ≤ ... ≤ an，求分解的种类数。

              示例：

              • 输入：a = 8
              • 输出：3（分解方式：8=2×2×2, 8=2×4, 8=8）

              回溯思路：

              1. 选择列表：从当前最小值开始，到√a结束（避免重复分解）。
              2. 路径记录：记录当前分解的因子。
              3. 终止条件：当乘积等于a时，记录结果；若乘积超过a，剪枝。

              4. 正整数分解问题的代码实现

              def factor_decomposition(a):
    if a == 1:
        return 0  # 题目要求因子大于1
    
    def backtrack(current_product, min_factor):
        # 如果当前乘积等于a，找到一种有效分解
        if current_product == a:
            return 1
        # 初始化分解方式数量
        count = 0
        # 从min_factor开始尝试所有可能的因子
        for i in range(min_factor, a + 1):
            # 剪枝：如果当前因子无法整除a或会导致乘积超过a，跳过
            if i > (a // current_product):
                break
            if a % i != 0:
                continue
            # 计算新的乘积
            new_product = current_product * i
            # 递归：继续分解剩余部分
            count += backtrack(new_product, i)
        return count
    
    # 从1开始分解（初始乘积为1，最小因子为2）
    return backtrack(1, 2)

# 测试示例
print(factor_decomposition(8))  # 输出: 3
print(factor_decomposition(12)) # 输出: 4（分解方式：12=2×2×3, 12=2×6, 12=3×4, 12=12）

              5. 代码解释与优化

              关键步骤解释：

              1. 递归函数参数：

                • current_product：当前分解的乘积
                • min_factor：当前允许的最小因子（确保因子递增）

              2. 剪枝优化：

                • 当i > (a // current_product)时，后续因子无法使乘积等于a，提前终止。
                • 只尝试能整除a的因子。

              3. 避免重复分解：

                • 通过min_factor确保后续选择的因子不小于当前因子。

              6. 练习题与拓展

              练习题：

              1. 编写函数生成所有可能的分解组合（如输入8，输出[[2,2,2], [2,4], [8]]）。
              2. 优化算法，处理大数分解（提示：使用动态规划或记忆化搜索）。

              拓展应用：

              • 完全数分解（如6=2×3）
              • 质因数分解（如12=2²×3）

              7. 回溯算法总结

              适用场景：

              • 问题可以分解为多个阶段的决策
              • 需要枚举所有可能的解
              • 存在剪枝条件以优化效率

              解题步骤：

              1. 定义问题的解空间
              2. 确定递归函数的参数
              3. 实现终止条件和结果收集
              4. 设计选择列表和剪枝条件
              5. 递归尝试所有可能的选择

              通过回溯算法，我们可以高效地解决各种组合优化问题，同时通过剪枝和记忆化技术进一步提升性能。

              • 1
              428
              已通过
              0
              题解被赞
              1. 关于
              2. 联系我们
              3. 隐私
              4. 服务条款
              5. 版权申诉
              6. Language
              7. 兼容模式
              8. 主题
              4. 在线咨询
              5. Worker 0, 40ms
              6. Powered by Hydro v4.13.3 Community