回溯算法是对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。
深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。此时对象类型变量就需要重置成为和之前一样，称为「状态重置」。
一、举个例子
力扣257. 二叉树的所有路径
这个题就适合用回溯，当遍历到叶节点时原路返回查找下一个叶节点
参考代码(go)：
二、回溯模板
1.对树形结构的回溯
backtrack(root TreeNode){
处理当前节点的值
backtrack(root.left) //处理左子树
backtrack(root.right) //处理右子树
撤销对当前节点的值的处理
}
2.对数组结构的回溯
backtrack(cur int, nums []int){
处理当前元素
backtrack(cur+1, nums) //处理下一个元素
撤销对当前元素的处理
backtrack(cur+1, nums) //处理下一个元素
}
(见下面题1)
可以根据题意对模板进行扩展，加上终止条件等，比如列举所有“合法”的序列
backtrack(cur int, nums []int){
if cur == len(nums){
//判断是否合法，更进一步判断是否重复，将满足条件的加入答案
ans = append(ans, sequence) //sequence为“合法”的序列
}
处理当前元素
backtrack(cur+1, nums) //处理下一个元素
撤销对当前元素的处理
backtrack(cur+1, nums) //处理下一个元素
}
在处理数组问题时，有时会要求列举出的序列不能重复，这时可以对上面的模板做一些调整。
通常我们对序列a,b使用回溯可以罗列下面四种情况（可以结合上面的模板，把a看成cur，b看成cur+1来理解）
1.处理a，处理b
2.处理a，不处理b
3.不处理a，处理b
4.不处理a，不处理b
在a和b相同的情况下，为了去重只需要罗列上面的3种情况，也就是去掉第2种或者第3种情况，处理逻辑如下（数组有序,这里去掉了第2种情况）
backtrack(cur int, nums []int, lastNum int){ //lastNum为上一个处理的元素
if cur == len(nums){
//判断是否合法，更进一步判断是否重复，将满足条件的加入答案
ans = append(ans, sequence) //sequence为“合法”的序列
}
处理当前元素
backtrack(cur+1, nums, nums[cur]) //处理下一个元素
撤销对当前元素的处理
if nums[cur]!=lastNum{
backtrack(cur+1, nums, lastNum) //处理下一个元素
}
}
(见下面题2)
去重的方式有很多种，还可以使用哈希表去重，或者像下面这样去重：
backtrack(cur int, freq [][]int){ //freq[i][1]是freq[i][0]的出现次数（类比哈希表统计数字出现的频率）
if cur == len(freq){
ans = append(ans, sequence) //sequence为唯一的序列
}
for i := 1; i <= freq[pos][1]; i++ {
处理i个当前元素 //比如s = append(s, freq[pos][0])
backtrack(cur+1) //处理下一个值不同的元素
}
撤销对freq[pos][1]个当前元素的处理 //比如s = s[:len(s)-freq[pos][1]]
backtrack(cur+1) //处理下一个值不同的元素
}
(见下面题3)
上面的去重是针对结果序列中，具有相同值的元素是相邻的，对于不相邻的元素有更通用的去重方法：
就像玩扑克牌一样，假设我们手中有4张2（♠♥♣♦就是这4张2的排列顺序），现在规定这4张2必须是按照♠♥♣♦的顺序打出去（可以分开出牌，不用同时打出去），最后在我们的出牌序列中，因为4张2的顺序规定好了，自然就达到了去重的目的。
backtrack(cur int, visits []bool, nums []int){ // cur是递归的深度，用来判断递归结束条件。visits[i]是数组nums[i]是否访问的标志
n := len(visits)
for i := 0; i < n; i++ {
if !visits[i]{
//只有在♠使用了之后才可以使用♥
if i > 0 && nums[i] == nums[i-1] && !visits[i-1] { //nums已经是排序好的数组
continue //当前不适合打2(♠或者♥)，但是可以打其他牌，所以使用continue而不是break或者return
}
visits[i] = true
处理当前元素
backtrack(cur+1, visits, nums)
撤销对当前元素的处理
visits[i] = false
}
}
}
(见下面题4)
3.对图结构的回溯
func backtrack(x int, graph [][]int){
//遍历连接x的节点
for _,y := range graph[x]{
//处理y
backtrack(y,graph) //寻找连接y的下一个节点
//撤销对y的处理
}
}
(见下面题5)
(见下面题6)
三、例题
题1
力扣78. 子集
func subsets(nums []int) [][]int {
ret := make([][]int, 0)
set := make([]int, 0)
n := len(nums)
var dfs func(pos int)
dfs = func(pos int){
if pos == n{
ret = append(ret, append([]int(nil), set...))
return
}
//选择当前元素
set = append(set, nums[pos])
dfs(pos+1)
//取消对当前元素的选择
set = set[:len(set)-1]
dfs(pos+1)
}
dfs(0)
return ret
}
题2
力扣491. 递增子序列
func findSubsequences(nums []int) [][]int {
ret := make([][]int, 0)
n := len(nums)
seq := make([]int, 0)
var dfs func(lastNum, pos int)
dfs = func(lastNum, pos int) {
if pos == n{
if len(seq)>=2{
ret = append(ret, append([]int(nil),seq...))
}
return
}
//保证序列递增
if nums[pos]>=lastNum{
seq = append(seq, nums[pos])
dfs(nums[pos], pos+1)
seq = seq[:len(seq)-1]
}
//根据模板，排除选择了a而不选择b的情况
if nums[pos] != lastNum{
dfs(lastNum, pos+1)
}
}
dfs(-101, 0)
return ret
}
题3
力扣90. 子集Ⅱ
func subsetsWithDup(nums []int) [][]int {
ret := make([][]int, 0)
s := make([]int, 0)
sort.Ints(nums)
freq := make([][2]int, 1)
freq[0] = [2]int{nums[0], 1}
n := len(nums)
//计算nums中元素出现的频率
for i:=1;i<n;i++{
n1 := len(freq)-1
if nums[i] == freq[n1][0]{
freq[n1][1]+=1
}else{
freq = append(freq, [2]int{nums[i], 1})
}
}
n2 := len(freq)
var dfs func(pos int)
dfs = func (pos int) {
if pos == n2{
ret = append(ret,append([]int(nil), s...))
return
}
for i := 1; i <= freq[pos][1]; i++ {
//选择i个当前值为freq[pos][0]的元素
s = append(s, freq[pos][0])
dfs(pos+1)
}
//撤销对freq[pos][1]个值为freq[pos][0]的元素的选择
s = s[:len(s)-freq[pos][1]]
dfs(pos+1)
}
dfs(0)
return ret
}
题4
力扣996. 正方形数组的数目
(来力扣不做996的程序员，只能度过一个相对失败的人生)
func numSquarefulPerms(nums []int) int {
n := len(nums)
visits := make([]bool, n)
ret := 0
sort.Ints(nums)
var dfs func(idx, pre int)
dfs = func(idx, pre int) {
if idx == n {
ret++
return
}
for i := 0; i < n; i++ {
if !visits[i] {
if i > 0 && nums[i] == nums[i-1] && !visits[i-1] { //去重
continue
}
visits[i] = true
if idx == 0 {
dfs(idx+1, nums[i])
} else {
sum := nums[i] + pre
flag := false
//判断是否为完全平方数
for l, r := 0, sum/2+1; l <= r; {
mid := (l + r) >> 1
p := mid * mid
if p < sum {
l = mid + 1
} else if p > sum {
r = mid - 1
} else {
flag = true
break
}
}
if flag {
dfs(idx+1, nums[i])
}
}
visits[i] = false
}
}
}
dfs(0, -1)
return ret
}
题5
力扣797. 所有可能的路径
func allPathsSourceTarget(graph [][]int) (ans [][]int) {
stk := []int{0}
var dfs func(int)
dfs = func(x int) {
if x == len(graph)-1 {
ans = append(ans, append([]int(nil), stk...))
return
}
for _, y := range graph[x] {
stk = append(stk, y)
dfs(y)
stk = stk[:len(stk)-1]
}
}
dfs(0)
return
}
题6
力扣996. 正方形数组的数目
(996值得二刷)
可以构建一个图，图中的点是数组A的所有元素，如果两个元素之和是平方数，则这两个元素（点）之间存在一条边（边可以指向自己），原题可以等价为求出从任意一个顶点（为了去重，起点的元素值不相同）开始的所有通路。
func numSquarefulPerms(nums []int) int {
n := len(nums)
count := make(map[int]int) //nums中的元素出现次数
graph := make(map[int][]int) //图的邻接表，若i+j为平方数，则i和j之间存在一条边
for _,num := range nums{
count[num]++
}
for k,_ := range count{
for k2,_ := range count{
//判断是否为完全平方数
sum := k + k2
flag := false
for l, r := 0, sum/2+1; l <= r; {
mid := (l + r) >> 1
p := mid * mid
if p < sum {
l = mid + 1
} else if p > sum {
r = mid - 1
} else {
flag = true
break
}
}
if flag {
if graph[k] == nil{
graph[k] = make([]int, 0)
}
graph[k] = append(graph[k], k2)
}
}
}
//x为去重后的数组中的元素， todo为需要排列的元素数量(初始为len(nums))
//只要x存在一条边通向y，且计数器count[y]大于0，则可以尝试将当前点设为y往后递归
var dfs func(x int, todo int)int
dfs = func(x int, todo int)int{
//选择元素x
count[x]-=1
ans := 1
if todo != 0{
ans = 0
for i:=0;i<len(graph[x]);i++{
//元素graph[x][i]的数量为0，continue查询其他元素
if count[graph[x][i]]==0{
continue
}
ans += dfs(graph[x][i], todo-1)
}
}
//不选择元素x
count[x]+=1
return ans
}
ret := 0
for k,_ := range graph{
ret += dfs(k, n-1)
}
return ret
}