回溯法

背景

回溯法(backtrack)常用于遍历列表所有子集,是 DFS 深度搜索一种,一般用于全排列,穷尽所有可能,遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!),它不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。

模板

1
result = []
2
func backtrack(选择列表,路径):
3
if 满足结束条件:
4
result.add(路径)
5
return
6
for 选择 in 选择列表:
7
做选择
8
backtrack(选择列表,路径)
9
撤销选择
Copied!
核心就是从选择列表里做一个选择,然后一直递归往下搜索答案,如果遇到路径不通,就返回来撤销这次选择。

示例

subsets

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
遍历过程
image.png
1
func subsets(nums []int) [][]int {
2
// 保存最终结果
3
result := make([][]int, 0)
4
// 保存中间结果
5
list := make([]int, 0)
6
backtrack(nums, 0, list, &result)
7
return result
8
}
9
10
// nums 给定的集合
11
// pos 下次添加到集合中的元素位置索引
12
// list 临时结果集合(每次需要复制保存)
13
// result 最终结果
14
func backtrack(nums []int, pos int, list []int, result *[][]int) {
15
// 把临时结果复制出来保存到最终结果
16
ans := make([]int, len(list))
17
copy(ans, list)
18
*result = append(*result, ans)
19
// 选择、处理结果、再撤销选择
20
for i := pos; i < len(nums); i++ {
21
list = append(list, nums[i])
22
backtrack(nums, i+1, list, result)
23
list = list[0 : len(list)-1]
24
}
25
}
Copied!
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集。
1
import (
2
"sort"
3
)
4
5
func subsetsWithDup(nums []int) [][]int {
6
// 保存最终结果
7
result := make([][]int, 0)
8
// 保存中间结果
9
list := make([]int, 0)
10
// 先排序
11
sort.Ints(nums)
12
backtrack(nums, 0, list, &result)
13
return result
14
}
15
16
// nums 给定的集合
17
// pos 下次添加到集合中的元素位置索引
18
// list 临时结果集合(每次需要复制保存)
19
// result 最终结果
20
func backtrack(nums []int, pos int, list []int, result *[][]int) {
21
// 把临时结果复制出来保存到最终结果
22
ans := make([]int, len(list))
23
copy(ans, list)
24
*result = append(*result, ans)
25
// 选择时需要剪枝、处理、撤销选择
26
for i := pos; i < len(nums); i++ {
27
// 排序之后,如果再遇到重复元素,则不选择此元素
28
if i != pos && nums[i] == nums[i-1] {
29
continue
30
}
31
list = append(list, nums[i])
32
backtrack(nums, i+1, list, result)
33
list = list[0 : len(list)-1]
34
}
35
}
Copied!
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
思路:需要记录已经选择过的元素,满足条件的结果才进行返回
1
func permute(nums []int) [][]int {
2
result := make([][]int, 0)
3
list := make([]int, 0)
4
// 标记这个元素是否已经添加到结果集
5
visited := make([]bool, len(nums))
6
backtrack(nums, visited, list, &result)
7
return result
8
}
9
10
// nums 输入集合
11
// visited 当前递归标记过的元素
12
// list 临时结果集(路径)
13
// result 最终结果
14
func backtrack(nums []int, visited []bool, list []int, result *[][]int) {
15
// 返回条件:临时结果和输入集合长度一致 才是全排列
16
if len(list) == len(nums) {
17
ans := make([]int, len(list))
18
copy(ans, list)
19
*result = append(*result, ans)
20
return
21
}
22
for i := 0; i < len(nums); i++ {
23
// 已经添加过的元素,直接跳过
24
if visited[i] {
25
continue
26
}
27
// 添加元素
28
list = append(list, nums[i])
29
visited[i] = true
30
backtrack(nums, visited, list, result)
31
// 移除元素
32
visited[i] = false
33
list = list[0 : len(list)-1]
34
}
35
}
Copied!
给定一个可包含重复数字的序列,返回所有不重复的全排列。
1
import (
2
"sort"
3
)
4
5
func permuteUnique(nums []int) [][]int {
6
result := make([][]int, 0)
7
list := make([]int, 0)
8
// 标记这个元素是否已经添加到结果集
9
visited := make([]bool, len(nums))
10
sort.Ints(nums)
11
backtrack(nums, visited, list, &result)
12
return result
13
}
14
15
// nums 输入集合
16
// visited 当前递归标记过的元素
17
// list 临时结果集
18
// result 最终结果
19
func backtrack(nums []int, visited []bool, list []int, result *[][]int) {
20
// 临时结果和输入集合长度一致 才是全排列
21
if len(list) == len(nums) {
22
subResult := make([]int, len(list))
23
copy(subResult, list)
24
*result = append(*result, subResult)
25
}
26
for i := 0; i < len(nums); i++ {
27
// 已经添加过的元素,直接跳过
28
if visited[i] {
29
continue
30
}
31
// 上一个元素和当前相同,并且没有访问过就跳过
32
if i != 0 && nums[i] == nums[i-1] && !visited[i-1] {
33
continue
34
}
35
list = append(list, nums[i])
36
visited[i] = true
37
backtrack(nums, visited, list, result)
38
visited[i] = false
39
list = list[0 : len(list)-1]
40
}
41
}
Copied!

练习

挑战题目
最近更新 1yr ago