backtrack 回溯算法

回溯算法（Backtracking）是一种通过递归尝试所有可能的解，并在不满足条件时回退的算法。它通常用于解决组合、排列、子集等问题。回溯算法的核心思想是 试探和回退，即在每一步尝试一个可能的解，如果发现当前解不满足条件，则回退到上一步，尝试其他可能的解。

---

回溯算法的基本框架

回溯算法通常使用递归实现，其基本框架如下：

func backtrack(参数) {
    if 满足结束条件 {
        将当前解加入结果列表
        return
    }

    for 选择 in 所有可能的选择 {
        做出选择
        backtrack(新参数) // 递归
        撤销选择
    }
}

---

回溯算法的关键点

1. 路径：
   • 当前已经做出的选择。
2. 选择列表：
   • 当前可以做的选择。
3. 结束条件：
   • 当路径满足条件时，将其加入结果列表。
4. 剪枝：
   • 在递归过程中，如果发现当前路径不可能满足条件，则提前终止递归。

---

回溯算法的应用场景

1. 组合问题：
   • 如从 [1, 2, 3] 中选出 2 个数的所有组合。
2. 排列问题：
   • 如 [1, 2, 3] 的所有排列。
3. 子集问题：
   • 如 [1, 2, 3] 的所有子集。
4. 搜索问题：
   • 如数独、八皇后问题。

---

回溯算法的经典问题

1. 组合问题

问题描述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

代码实现：

func combine(n int, k int) [][]int {
    result := [][]int{}
    backtrack(n, k, 1, []int{}, &result)
    return result
}

func backtrack(n, k, start int, current []int, result *[][]int) {
    if len(current) == k {
        combination := make([]int, k)
        copy(combination, current)
        *result = append(*result, combination)
        return
    }

    for i := start; i <= n; i++ {
        current = append(current, i)
        backtrack(n, k, i+1, current, result)
        current = current[:len(current)-1]
    }
}

---

2. 排列问题

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

代码实现：

func permute(nums []int) [][]int {
    result := [][]int{}
    backtrack(nums, []int{}, &result)
    return result
}

func backtrack(nums []int, current []int, result *[][]int) {
    if len(current) == len(nums) {
        permutation := make([]int, len(nums))
        copy(permutation, current)
        *result = append(*result, permutation)
        return
    }

    for i := 0; i < len(nums); i++ {
        if contains(current, nums[i]) {
            continue
        }
        current = append(current, nums[i])
        backtrack(nums, current, result)
        current = current[:len(current)-1]
    }
}

func contains(arr []int, target int) bool {
    for _, num := range arr {
        if num == target {
            return true
        }
    }
    return false
}

---

3. 子集问题

问题描述：给定一个整数数组 nums，返回其所有可能的子集。

代码实现：

func subsets(nums []int) [][]int {
    result := [][]int{}
    backtrack(nums, 0, []int{}, &result)
    return result
}

func backtrack(nums []int, start int, current []int, result *[][]int) {
    subset := make([]int, len(current))
    copy(subset, current)
    *result = append(*result, subset)

    for i := start; i < len(nums); i++ {
        current = append(current, nums[i])
        backtrack(nums, i+1, current, result)
        current = current[:len(current)-1]
    }
}

---

4. 八皇后问题

问题描述：在 8x8 的棋盘上放置 8 个皇后，使得它们互不攻击。

代码实现：

func solveNQueens(n int) [][]string {
    result := [][]string{}
    board := make([]int, n) // board[i] 表示第 i 行的皇后放在第 board[i] 列
    backtrack(n, 0, board, &result)
    return result
}

func backtrack(n, row int, board []int, result *[][]string) {
    if row == n {
        solution := make([]string, n)
        for i := 0; i < n; i++ {
            s := make([]byte, n)
            for j := 0; j < n; j++ {
                if j == board[i] {
                    s[j] = 'Q'
                } else {
                    s[j] = '.'
                }
            }
            solution[i] = string(s)
        }
        *result = append(*result, solution)
        return
    }

    for col := 0; col < n; col++ {
        if isValid(board, row, col) {
            board[row] = col
            backtrack(n, row+1, board, result)
            board[row] = -1
        }
    }
}

func isValid(board []int, row, col int) bool {
    for i := 0; i < row; i++ {
        if board[i] == col || abs(board[i]-col) == abs(i-row) {
            return false
        }
    }
    return true
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

---

回溯算法的优化

1. 剪枝：
   • 在递归过程中，如果发现当前路径不可能满足条件，则提前终止递归。
   • 例如，在组合问题中，通过 start 参数避免重复组合。
2. 记忆化：
   • 在某些问题中，可以使用记忆化技术避免重复计算。

---

总结

回溯算法是一种通用的解题方法，适用于组合、排列、子集等问题。通过递归和剪枝，可以高效地生成所有可能的解。掌握回溯算法的基本框架和关键点，能够帮助解决许多复杂的搜索问题。