码海

# 回溯算法基础

# 简介

回溯算法（Backtracking）是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来尝试找到正确的解。

# 基本思想

  1. 构造候选解：按照一定的规则，逐步构造候选解
  2. 判断条件：检查当前构造的候选解是否满足问题的约束条件
  3. 回溯过程：如果当前候选解不满足条件，则回退到上一步，尝试其他可能的选择

# 实现框架

function backtrack(选择列表, 路径) {
    if (满足结束条件) {
        result.add(路径);
        return;
    }
    
    for (选择 in 选择列表) {
        做选择;
        backtrack(选择列表, 路径);
        撤销选择;
    }
}

# 经典问题

# 1. N皇后问题

function solveNQueens(n) {
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    const result = [];
    
    function isValid(row, col) {
        // 检查列
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // 检查左上方
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // 检查右上方
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    }
    
    function backtrack(row) {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (!isValid(row, col)) continue;
            
            board[row][col] = 'Q';
            backtrack(row + 1);
            board[row][col] = '.';
        }
    }
    
    backtrack(0);
    return result;
}

# 2. 子集问题

function subsets(nums) {
    const result = [];
    const track = [];
    
    function backtrack(start) {
        result.push([...track]);
        
        for (let i = start; i < nums.length; i++) {
            track.push(nums[i]);
            backtrack(i + 1);
            track.pop();
        }
    }
    
    backtrack(0);
    return result;
}

# 应用场景

  1. 组合问题：从n个数中选择k个数的所有组合
  2. 排列问题：n个数的所有排列
  3. 切割问题：将字符串切割成符合条件的子串
  4. 子集问题：求一个集合的所有子集
  5. 棋盘问题：N皇后、数独等

# 优化策略

  1. 剪枝：尽早判断当前路径是否可行，避免无效搜索
  2. 状态记录：使用合适的数据结构记录状态，避免重复计算
  3. 约束传播：利用问题的特殊性质减少搜索空间

# 复杂度分析

  • 时间复杂度：通常为O(N!)或O(2^N)，具体取决于问题
  • 空间复杂度：通常为O(N)，用于保存递归调用栈

# 注意事项

  1. 回溯算法的效率通常不高，需要考虑是否有更优的解法
  2. 合理的剪枝可以大大提高效率
  3. 注意递归调用的层数，防止栈溢出
  4. 状态的恢复很重要，确保回溯时能正确还原状态

# 练习建议

  1. 从简单的排列组合问题开始
  2. 理解「选择」和「路径」的概念
  3. 掌握回溯算法的代码框架
  4. 练习不同类型的回溯问题，总结解题模式
  5. 注意优化，尤其是剪枝的应用

← 最短路径算法 →