回溯算法完全指南 🌲

一、什么是回溯算法？ 🤔

1. 通俗理解

想象你在走迷宫 🏃‍♂️：

• 遇到岔路口时，选择一条路继续走
• 发现走不通时，退回岔路口，选择另一条路
• 不断重复这个过程，直到找到出口

这就是回溯算法的核心思想！

2. 适用场景

回溯算法常用来解决以下问题：

• 组合问题：从N个数中找出k个数的所有可能 📦
• 切割问题：把字符串切成符合条件的多个部分 ✂️
• 子集问题：求一个集合的所有子集 🎯
• 排列问题：N个数的所有排列方式 🔄
• 棋盘问题：N皇后、数独等 ♟️

二、回溯算法模板 📝

1. 核心框架

function backtrack(路径, 选择列表) {
    if (满足结束条件) {
        保存结果;
        return;
    }
    
    for (选择 of 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;
    }
}

2. 实战示例：全排列问题 ⭐

function permute(nums) {
    const result = [];
    const track = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack() {
        // 到达叶子节点，收集结果
        if (track.length === nums.length) {
            result.push([...track]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            // 已经使用过的数字跳过
            if (used[i]) continue;
            
            // 做选择
            track.push(nums[i]);
            used[i] = true;
            
            // 进入下一层决策树
            backtrack();
            
            // 取消选择
            track.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return result;
}

// 使用示例
console.log(permute([1, 2, 3]));
// 输出：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

三、经典问题解析 🔍

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. 剪枝优化

在搜索中及早判断，避免无效的搜索路径：

if (不满足条件) continue; // 剪枝

2. 状态重置

确保在回溯时正确重置状态：

// 做选择
track.push(choice);
used[i] = true;

backtrack();

// 撤销选择
track.pop();
used[i] = false;

五、实战应用 🚀

1. 路径规划

function findPath(maze, start, end) {
    const path = [];
    const visited = new Set();
    
    function backtrack(current) {
        if (current === end) {
            return true;
        }
        
        for (const next of getNeighbors(current)) {
            if (visited.has(next) || !isValid(maze, next)) continue;
            
            path.push(next);
            visited.add(next);
            
            if (backtrack(next)) return true;
            
            path.pop();
            visited.delete(next);
        }
        
        return false;
    }
    
    return backtrack(start) ? path : null;
}

2. 表单验证组合

function validateCombinations(rules) {
    const result = [];
    const current = [];
    
    function backtrack(start) {
        if (isValid(current)) {
            result.push([...current]);
        }
        
        for (let i = start; i < rules.length; i++) {
            current.push(rules[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return result;
}

六、性能分析 📊

问题类型	时间复杂度	空间复杂度
排列问题	O(n!)	O(n)
组合问题	O(2^n)	O(n)
N皇后	O(n!)	O(n)

七、常见误区 ⚠️

1. 忘记状态重置
2. 递归终止条件不明确
3. 剪枝条件过于宽松或严格
4. 没有考虑重复情况

八、练习推荐 📝

1. LeetCode 46: 全排列
2. LeetCode 78: 子集
3. LeetCode 51: N皇后
4. LeetCode 17: 电话号码的字母组合

九、扩展阅读 📚

• 回溯算法详解
• 回溯vs动态规划
• 实战案例分析