回溯算法解题套路框架

[TOC] ## 概述 * 回溯法是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。 * 回溯算法就是个多叉树的遍历问题 解决一个回溯问题，实际上就是一个决策树的遍历过程 1. 路径：也就是已经做出的选择。 2. 选择列表：也就是你当前可以做的选择。 3. 结束条件：也就是到达决策树底层，无法再做选择的条件。 回溯算法框架 ``` result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 ``` > 其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」 如枚举 1,2,3,列出回溯算法的「决策树」   现在可以解答开头的几个名词：\[2\] 就是**路径**，记录你已经做过的选择；\[1,3\] 就是**选择列表**，表示你当前可以做出的选择；**结束条件**就是遍历到树的底层，在这里就是选择列表为空的时候。 **前序和后续后序排列**  前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。  这样可以更好的理解回溯算法 ``` for 选择 in 选择列表: # 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) # 撤销选择 路径.remove(选择) 将该选择再加入选择列表 ``` 我们只要在递归之前做出选择，在递归之后撤销刚才的选择 回溯算法 go 实现

server.go

``` import ( "fmt" ) var group [][]int func permute(nums []int) [][]int { group =make([][]int,0) if len(nums) == 0 { return group } // 存储已经用过的值,遍历共用一个 状态 used := make([]bool, len(nums)) track := make([]int, 0,len(nums)) backtrack(nums, track, used) return group } func backtrack(nums []int, track []int, used []bool) { if len(nums) == len(track) { tmp := make([]int, len(track)) // 拷贝切片值 copy(tmp, track) group = append(group, tmp) return } for i := 0; i < len(nums); i++ { if !used[i] { used[i]=true track = append(track, nums[i]) backtrack(nums,track, used) // 撤销状态 used[i]=false track=track[:len(track)-1] } } } func main() { fmt.Printf("%+v\n", permute([]int{1,2,3})) //[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]] } ```

回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高点赞