回溯算法介绍与基本使用

1. 什么是回溯算法？

回溯算法（Backtracking）是一种通过试错来寻找问题解决方案的算法思想。它通过逐步构建候选解，并在确定当前路径无法得到有效解时，回溯到上一步尝试其他可能的路径。回溯算法常用于解决组合优化、排列组合、子集生成等需要遍历所有可能性的问题。

2. 回溯算法的基本思想

试错思想：通过递归或迭代逐步构建候选解
剪枝操作：当发现当前路径不可能得到解时，提前终止该路径
状态管理：在递归过程中维护和恢复状态（通过栈或参数传递）

3. 适用场景

✅ 组合问题：从n个元素中选k个的所有组合
✅ 排列问题：全排列、N皇后问题
✅ 子集问题：求集合的所有子集
✅ 分割问题：字符串分割为回文子串
✅ 棋盘问题：数独、单词搜索

4. 算法基本结构

def backtrack(路径, 选择列表):
    if 满足结束条件:
        结果集.append(路径)
        return
    
    for 选择 in 选择列表:
        if 不满足剪枝条件:
            做选择（加入路径）
            backtrack(新路径, 新选择列表)
            撤销选择（从路径移除）

5. 常见回溯算法问题

5.1 全排列问题

给定一个不含重复数字的数组，返回其所有可能的全排列。

def permute(nums):
    def backtrack(first = 0):
        # 所有数都填完了
        if first == n:
            output.append(nums[:])
        for i in range(first, n):
            # 动态维护数组
            nums[first], nums[i] = nums[i], nums[first]
            # 继续递归填下一个数
            backtrack(first + 1)
            # 撤销操作
            nums[first], nums[i] = nums[i], nums[first]
    
    n = len(nums)
    output = []
    backtrack()
    return output

5.2 N皇后问题

n 皇后问题是指在一个 n×n 的棋盘上放置 n 个皇后，使得它们互不攻击。皇后可以攻击同一行、同一列以及同一对角线上的其他棋子。

def solveNQueens(n):
    def def(board, row):
        if row == n:
            board_as_strings = [''.join(row) for row in board]
            result.append(board_as_strings)
            return
        for col in range(n):
            if isValid(board, row, col):
                board[row][col] = 'Q'
                def(board, row + 1)
                board[row][col] = '.'

    def isValid(board, row, col):
        if board[row][col] == 'Q':
            return False
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        return True

    board = [['.'] * n for _ in range(n)]
    result = []
    def(board, 0)
    return result

5.3 子集问题

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

def subsets(nums):
    def backtrack(first = 0, curr = []):
        # 将当前子集加入结果集
        result.append(curr[:])
        for i in range(first, n):
            # 将当前元素加入子集
            curr.append(nums[i])
            # 递归生成下一个子集
            backtrack(i + 1, curr)
            # 撤销选择
            curr.pop()

    n = len(nums)
    result = []
    backtrack()
    return result

5.4 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回所有可能的分割方案。

def partition(s):
    def isPalindrome(s):
        return s == s[::-1]

    def backtrack(start, path):
        if start == n:
            result.append(path)
            return
        for i in range(start, n):
            if isPalindrome(s[start:i + 1]):
                backtrack(i + 1, path + [s[start:i + 1]])

    n = len(s)
    result = []
    backtrack(0, [])
    return result