回溯算法模板总结_回溯模板

回溯算法是对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。
深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。此时对象类型变量就需要重置成为和之前一样，称为「状态重置」。
1
2

一、举个例子

力扣257. 二叉树的所有路径

这个题就适合用回溯，当遍历到叶节点时原路返回查找下一个叶节点
参考代码(go)：

二、回溯模板

1.对树形结构的回溯

backtrack(root TreeNode){
	处理当前节点的值
	backtrack(root.left)  //处理左子树
	backtrack(root.right)  //处理右子树
	撤销对当前节点的值的处理
}
1
2
3
4
5
6

2.对数组结构的回溯

backtrack(cur int, nums []int){
	处理当前元素
	backtrack(cur+1, nums)  //处理下一个元素
	撤销对当前元素的处理
	backtrack(cur+1, nums)  //处理下一个元素
}
1
2
3
4
5
6

(见下面题1)

可以根据题意对模板进行扩展，加上终止条件等，比如列举所有“合法”的序列

backtrack(cur int, nums []int){
	if cur == len(nums){
		//判断是否合法，更进一步判断是否重复，将满足条件的加入答案
		ans = append(ans, sequence) //sequence为“合法”的序列
	}
	处理当前元素
	backtrack(cur+1, nums)  //处理下一个元素
	撤销对当前元素的处理
	backtrack(cur+1, nums)  //处理下一个元素
}
1
2
3
4
5
6
7
8
9
10

在处理数组问题时，有时会要求列举出的序列不能重复，这时可以对上面的模板做一些调整。
通常我们对序列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)  //处理下一个元素
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

(见下面题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) //处理下一个值不同的元素
}
1
2
3
4
5
6
7
8
9
10
11

(见下面题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
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(见下面题4)

3.对图结构的回溯

func backtrack(x int, graph [][]int){
	//遍历连接x的节点
	for _,y := range graph[x]{
		//处理y
		backtrack(y,graph) //寻找连接y的下一个节点
		//撤销对y的处理
	}
}
1
2
3
4
5
6
7
8

(见下面题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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

题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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

题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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

题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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64