回溯

回溯算法是一种通过探索所有可能的候选解来找出所有解的问题的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃它，即“回溯”并且尝试新的选项。回溯通常用于解决约束满足问题，其中包括组合问题、划分问题、子集问题等。

回溯算法的通用思路可以概括为以下几个步骤：

选择：从候选解中选择一个可能的分支。
约束：检查这个分支是否符合约束条件，如果不符合，剪枝。
目标：检查当前分支是否满足解的条件，如果满足，将其加入解集。
递归：对剩下的候选解重复上述步骤。
回溯：如果当前分支已经到达末端，或者不满足解的条件，则返回上一步，尝试其他可能的分支。

在 Go 语言中实现回溯算法，可以通过递归函数来模拟这个过程。下面是一个使用 Go 语言实现的回溯算法的代码示例，这个例子是解决组合问题的，即从 1 到 n 的整数中选出 k 个数的所有可能组合。

package main

import "fmt"

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

func backtrack(start, n, k int, temp *[]int, result *[][]int) {
    // 如果组合的长度已经满足k，则将其加入结果集
    if len(*temp) == k {
        comb := make([]int, k)
        copy(comb, *temp)
        *result = append(*result, comb)
        return
    }
    // 从start开始尝试每个可能的选项
    for i := start; i <= n; i++ {
        *temp = append(*temp, i) // 选择当前数
        backtrack(i+1, n, k, temp, result) // 递归
        *temp = (*temp)[:len(*temp)-1] // 回溯，撤销选择
    }
}

func main() {
    n := 4
    k := 2
    combinations := combine(n, k)
    for _, comb := range combinations {
        fmt.Println(comb)
    }
}

在这个代码中，combine 函数初始化结果集和临时数组，然后调用 backtrack 函数开始回溯。backtrack 函数是递归的，它会尝试所有可能的组合，并且在满足条件时将其添加到结果集中。当递归调用返回时，它会撤销当前的选择（这就是回溯的部分），然后尝试下一个选项。

这个通用的回溯框架可以应用于许多其他类型的问题，比如排列问题、子集问题等，只需要根据具体问题调整选择、约束和目标的处理即可。

hot-100

回溯