回溯算法（Backtracking）

leetcode
● 46.全排列
● 78.子集

认识

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

是一种渐进式寻找并构建问题解决方式的策略。回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。

回溯算法的特点

1. 系统性：系统地搜索解空间
2. 试探性：在搜索过程中进行试探
3. 回溯性：当发现当前路径不可能得到解时，回溯到上一步
4. 递归性：通常使用递归实现

回溯算法的适用场景

1. 组合问题：如组合、排列、子集等
2. 切割问题：如字符串分割、数组分割等
3. 棋盘问题：如N皇后、数独等
4. 图搜索问题：如迷宫、路径等
5. 调度问题：如任务分配、时间表安排等

回溯算法的原理

回溯算法的基本原理可以概括为以下步骤：

1. 定义解空间：确定问题的所有可能解
2. 组织解空间：使用树或图结构组织解空间
3. 搜索解空间：深度优先搜索解空间
4. 剪枝：提前终止不可能产生解的分支
5. 记录解：当找到可行解时记录

回溯算法的框架：

function backtrack(当前状态) {
    if (满足结束条件) {
        记录解;
        return;
    }
    
    for (每个可能的选择) {
        if (选择有效) {
            做出选择;
            backtrack(新状态);
            撤销选择; // 回溯
        }
    }
}

JavaScript中的回溯算法应用

1. 组合问题

// 组合问题：从1到n中选取k个数的所有组合
function combine(n, k) {
    const result = [];
    
    function backtrack(start, current) {
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        
        for (let i = start; i <= n; i++) {
            current.push(i);
            backtrack(i + 1, current);
            current.pop(); // 回溯
        }
    }
    
    backtrack(1, []);
    return result;
}

// 使用示例
console.log(combine(4, 2));
// 输出: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

2. 排列问题

// 排列问题：生成数组的所有排列
function permute(nums) {
    const result = [];
    
    function backtrack(current, used) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                current.push(nums[i]);
                backtrack(current, used);
                current.pop(); // 回溯
                used[i] = false; // 回溯
            }
        }
    }
    
    backtrack([], new Array(nums.length).fill(false));
    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]]

3. 子集问题

// 子集问题：生成数组的所有子集
function subsets(nums) {
    const result = [];
    
    function backtrack(start, current) {
        result.push([...current]);
        
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop(); // 回溯
        }
    }
    
    backtrack(0, []);
    return result;
}

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

4. N皇后问题

// N皇后问题：在N×N棋盘上放置N个皇后，使得它们互不攻击
function solveNQueens(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    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)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.'; // 回溯
            }
        }
    }
    
    backtrack(0);
    return result;
}

// 使用示例
console.log(solveNQueens(4));
/* 输出:
[
    [".Q..","...Q","Q...","..Q."],
    ["..Q.","Q...","...Q",".Q.."]
]
*/

5. 数独求解

// 数独求解：使用回溯算法解决数独
function solveSudoku(board) {
    function isValid(row, col, num) {
        // 检查行
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === num) return false;
        }
        
        // 检查列
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === num) return false;
        }
        
        // 检查3×3宫格
        const boxRow = Math.floor(row / 3) * 3;
        const boxCol = Math.floor(col / 3) * 3;
        for (let i = boxRow; i < boxRow + 3; i++) {
            for (let j = boxCol; j < boxCol + 3; j++) {
                if (board[i][j] === num) return false;
            }
        }
        
        return true;
    }
    
    function backtrack() {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    for (let num = 1; num <= 9; num++) {
                        if (isValid(row, col, num.toString())) {
                            board[row][col] = num.toString();
                            if (backtrack()) return true;
                            board[row][col] = '.'; // 回溯
                        }
                    }
                    return false; // 没有数字可以填入
                }
            }
        }
        return true; // 所有格子都已填满
    }
    
    backtrack();
    return board;
}

// 使用示例
const board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
];
console.log(solveSudoku(board));
// 输出: 解决后的数独板

6. 分割回文串

// 分割回文串：将字符串分割成所有可能的回文串分割
function partition(s) {
    const result = [];
    
    function isPalindrome(str, left, right) {
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    
    function backtrack(start, current) {
        if (start === s.length) {
            result.push([...current]);
            return;
        }
        
        for (let end = start; end < s.length; end++) {
            if (isPalindrome(s, start, end)) {
                current.push(s.substring(start, end + 1));
                backtrack(end + 1, current);
                current.pop(); // 回溯
            }
        }
    }
    
    backtrack(0, []);
    return result;
}

// 使用示例
console.log(partition("aab"));
// 输出: [["a","a","b"], ["aa","b"]]

回溯算法的优化技巧

1. 剪枝：提前终止不可能产生解的分支
2. 记忆化：缓存中间结果，避免重复计算
3. 迭代实现：使用栈代替递归，避免栈溢出
4. 位运算：使用位掩码表示状态，优化空间
5. 顺序优化：合理安排搜索顺序

回溯算法与DFS的关系

回溯算法可以看作是带有剪枝的深度优先搜索（DFS）。它们的关系：

• DFS：系统地搜索整个解空间
• 回溯：在DFS基础上，添加剪枝和回溯操作
• 共同点：都使用递归，都是深度优先搜索
• 不同点：回溯会撤销选择，而DFS通常不会

回溯算法的时间复杂度分析

回溯算法的时间复杂度通常与解空间的规模有关：

• 最坏情况：O(n!) - 如排列问题
• 一般情况：O(2^n) - 如子集问题
• 优化后：可能显著降低

回溯算法的注意事项

1. 状态管理：正确维护当前状态
2. 边界条件：明确结束条件和剪枝条件
3. 解的记录：正确记录和复制解
4. 递归深度：注意递归深度限制
5. 性能优化：考虑剪枝和记忆化