回溯算法：解锁多种问题的解决之门
经典回溯算法
回溯算法是一种基于深度优先搜索的算法，通过探索所有可能的候选解来找出所有可能的解。当候选解不满足条件时，会回溯到上一步，尝试其他的候选解。下面将介绍回溯算法在组合问题、切割问题、排列问题、子集问题、棋盘问题和图的遍历等方面的应用。
组合问题
如从 N 个数中选出 k 个数的所有组合方式。以从数组 [1,2,3,4] 中选 2 个数为例，其核心思想是通过回溯的方式尝试所有可能的组合。具体步骤如下：
- 初始化 ：定义结果集和路径变量，结果集用于存储所有满足条件的组合，路径变量用于存储当前递归路径上的元素。
- 递归函数 ：参数包括起始位置 startindex、目标个数 k、数组等。终止条件是路径的长度等于 k 时，将路径添加到结果集中。在循环中，从 startindex 开始遍历数组，依次将元素添加到路径中，并递归调用函数，起始位置加 1，继续选择下一个元素。回溯时移除路径中的最后一个元素。
- 代码演示 ：
func combine(n int, k int) [][]int {result := [][]int{}path := []int{}var backtrack func(startIndex int)backtrack = func(startIndex int) {if len(path) == k {temp := make([]int, k)copy(temp, path)result = append(result, temp)return}for i := startIndex; i <= n; i++ {path = append(path, i)backtrack(i + 1)path = path[:len(path)-1]}}backtrack(1)return result
}
切割问题
一个字符串按一定规则有几种切割方式。例如将字符串 “aab” 切割成所有可能的子字符串组合。其核心思想是通过回溯的方式尝试所有可能的切割位置。具体步骤如下：
- 初始化 ：定义结果集和路径变量。
- 递归函数 ：参数包括起始位置 startindex、字符串等。终止条件是起始位置等于字符串长度时，将路径添加到结果集中。在循环中，从 startindex 开始遍历字符串，依次切割子字符串，判断是否符合要求，如果符合，就将其添加到路径中，并递归调用函数，起始位置更新为 i+1。回溯时移除路径中的最后一个元素。
- 代码演示 ：
func partition(s string) [][]string {result := [][]string{}path := []string{}var backtrack func(startIndex int)backtrack = func(startIndex int) {if startIndex >= len(s) {temp := make([]string, len(path))copy(temp, path)result = append(result, temp)return}for i := startIndex; i < len(s); i++ {if isPalindrome(s[startIndex : i+1]) {path = append(path, s[startIndex:i+1])backtrack(i + 1)path = path[:len(path)-1]}}}backtrack(0)return result
}
func isPalindrome(s string) bool {for i := 0; i < len(s)/2; i++ {if s[i] != s[len(s)-1-i] {return false}}return true
}
排列问题
如 N 个数的所有排列方式。以数组 [1,2,3] 的全排列为例。其核心思想是通过回溯的方式尝试所有可能的排列。具体步骤如下：
- 初始化 ：定义结果集和路径变量，同时定义一个 used 数组来记录元素是否被使用。
- 递归函数 ：参数包括 used 数组等。终止条件是路径的长度等于数组长度时，将路径添加到结果集中。在循环中，依次选择未使用的元素，将其添加到路径中，并标记为已使用，递归调用函数。回溯时移除路径中的最后一个元素，并标记为未使用。
- 代码演示 ：
func permute(nums []int) [][]int {result := [][]int{}path := []int{}used := make([]bool, len(nums))var backtrack func()backtrack = func() {if len(path) == len(nums) {temp := make([]int, len(path))copy(temp, path)result = append(result, temp)return}for i := 0; i < len(nums); i++ {if !used[i] {used[i] = truepath = append(path, nums[i])backtrack()path = path[:len(path)-1]used[i] = false}}}backtrack()return result
}
子集问题
如从 N 个数中选出所有符合条件的子集。以数组 [1,2,3] 的所有子集为例。其核心思想是通过回溯的方式尝试所有可能的子集。具体步骤如下：
- 初始化 ：定义结果集和路径变量。
- 递归函数 ：参数包括起始位置 startindex、数组等。终止条件是当起始位置大于等于数组长度时结束。在循环中，从 startindex 开始遍历数组，依次将元素添加到路径中，并添加到结果集中，然后递归调用函数，起始位置加 1，继续向下搜索。回溯时移除路径中的最后一个元素。
- 代码演示 ：
func subsets(nums []int) [][]int {result := [][]int{}path := []int{}var backtrack func(startIndex int)backtrack = func(startIndex int) {temp := make([]int, len(path))copy(temp, path)result = append(result, temp)for i := startIndex; i < len(nums); i++ {path = append(path, nums[i])backtrack(i + 1)path = path[:len(path)-1]}}backtrack(0)return result
}
棋盘问题
经典的八皇后问题是回溯算法在棋盘问题中的典型应用。其核心思想是通过回溯的方式尝试在棋盘上放置皇后。具体步骤如下：
- 初始化 ：定义棋盘和结果集。
- 递归函数 ：参数包括行号 row 等。终止条件是当行号等于棋盘大小时，将当前棋盘状态添加到结果集中。在循环中，依次尝试在当前行的每一列放置皇后，判断是否满足条件，如果满足，就在此位置放置皇后，并递归调用函数，行号加 1。回溯时撤销皇后的位置。
- 代码演示 ：
func solveNQueens(n int) [][]string {result := [][]string{}board := make([][]string, n)for i := range board {board[i] = make([]string, n)for j := range board[i] {board[i][j] = "."}}var backtrack func(row int)backtrack = func(row int) {if row == n {temp := make([]string, n)for i := range board {temp[i] = strings.Join(board[i], "")}result = append(result, temp)return}for col := 0; col < n; col++ {if isValid(board, row, col) {board[row][col] = "Q"backtrack(row + 1)board[row][col] = "."}}}backtrack(0)return result
}
func isValid(board [][]string, row, col int) bool {for i := 0; i < row; i++ {if board[i][col] == "Q" {return false}}for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {if board[i][j] == "Q" {return false}}for i, j := row-1, col+1; i >= 0 && j < len(board); i, j = i-1, j+1 {if board[i][j] == "Q" {return false}}return true
}
图的遍历
深度优先搜索（DFS）是回溯算法在图的遍历中的典型应用。其核心思想是通过回溯的方式深度优先地遍历图。具体步骤如下：
- 初始化 ：定义访问标记数组，用于记录节点是否被访问过。
- 递归函数 ：参数包括当前节点等。终止条件是当所有节点都被访问过时结束。将当前节点标记为已访问，并依次访问其邻接节点，若邻接节点未被访问过，则递归调用函数。回溯时将当前节点标记为未访问。
- 代码演示 ：
func DFS(graph [][]int, start int) {visited := make([]bool, len(graph))var dfs func(v int)dfs = func(v int) {visited[v] = truefmt.Print(v, " ")for _, w := range graph[v] {if !visited[w] {dfs(w)}}}dfs(start)
}