回溯算法 (Backtracking)

概述

难度：⭐⭐⭐ 分类：搜索与优化 (Search & Optimization)

回溯算法是一种通过枚举所有可能来找到问题解的算法思想。它采用试错的方式，在搜索过程中如果发现当前选择无法达成目标，就回退到上一步重新选择。

Backtracking is an algorithm paradigm that finds solutions by trying all possible candidates. It uses a trial-and-error approach, retreating when a path fails to lead to a valid solution.

核心思想

回溯 = 递归 + 剪枝

选择：从当前状态做出一个选择
探索：递归进入下一层
撤销：回退选择，尝试其他可能
剪枝：提前排除不可能的情况

经典应用

1. 全排列问题

def permute(nums):
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    backtrack([], [False] * len(nums))
    return result

2. N皇后问题

在 N×N 的棋盘上放置 N 个皇后，使得它们互不攻击。

def solveNQueens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def is_valid(row, col):
        # 检查列
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        # 检查左上角
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        # 检查右上角
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        for col in range(n):
            if not is_valid(row, col):
                continue
            board[row][col] = 'Q'
            backtrack(row + 1)
            board[row][col] = '.'
    
    backtrack(0)
    return result

3. 子集问题

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

复杂度分析

时间复杂度：O(n!) 或 O(2^n)，通常需要剪枝优化
空间复杂度：O(n)，递归栈深度

适用条件

问题可以分解为「选择 → 状态更新 → 回溯」的模式
需要枚举所有可能的解
解空间可以通过剪枝缩小

💡 记忆口诀

回溯算法三步走：选、搜、撤。全排列用Used数组，N皇后检查三方向。子集问题先加入，排列组合不混淆。

排列组合要分清，排列讲究顺序，组合不讲究顺序。