回溯#

终于来到回溯了，树真的😔

理论基础#

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯就会有递归，两者相辅相成
回溯一般来说就在递归的下面
回溯函数 – 递归函数
回溯法 是一个纯暴力的搜索，并不🤡有什么技巧，只是一个遍历所有可能性的过程,因此回溯法并不高效
回溯法解决的问题：

  1. 组合问题：N个数里面按一定规则找出k个数的集合
  2. 切割问题：一个字符串按一定规则有几种切割方式
  3. 子集问题：一个N个数的集合里有多少符合条件的子集
  4. 排列问题：N个数按一定规则全排列，有几种排列方式
  5. 棋盘问题：N皇后，解数独等等
  6. 深度优先遍历问题：如图、树的遍历
    所有的回溯法都可以抽象为一个树形结构，通过这些树形结构去理解回溯法会比较容易

一般回溯法的框架如下：

1
2
3
4
5
6
7
8
9
10
11
func backTracking(....args any) {
	if 满足结束条件{
	 	 收集结果
  	 return
	 }
	for 选择 in 选择列表 {
		处理节点
         backTracking（路径,选择列表）  // 递归
		回溯，撤销处理结果
	}
}

OK，直接做题目吧

组合#

注意：#

重新回过来看我的回溯理解的时候我发现这里有问题，我被上面两道题的诱导会觉得回溯一定是要在同一个数组上进行操作才行，实则不然

我需要把从上往下遍历的回溯想象成 有一个个箱子，然后这些箱子组成了一棵树，每次就是从这棵树里取出一个值拼在一起就是这么简单

所以回溯实际回溯的是path这个数组，通过path数组的不断的增长减少来遍历每种情况，就是这样，以上.

至于剪枝问题，就是考虑一些特殊情况，比如说我需要凑9个数，但是我剩余就只有8个数了，那么我就不需要再去遍历了，就这么简单

所以为什么这些组合问题各有各的不同，却又都是组合问题呢，究其本源一般都是题目给你一个数组，然后他会告诉你一些限定条件，你需要通过这些限定条件使得你每次取的箱子都是不完整的箱子，而这些不完整度是跟上下文的调用有关系的（传参）。

组合问题#

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

如果不理解，就看图

如果还是不理解其中的原理，不妨直接debug，就会知道他具体的运行流程

77.组合1

感谢代码随想录。

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
var (
	path []int
	res  [][]int
)

func combine(n int, k int) [][]int {
	path, res = make([]int, 0, n), make([][]int, 0)
	dfs(1, n, k)
	return res
}

func dfs(start int, n int, k int) {
	if len(path) == k {
		temp := make([]int, k)
		copy(temp, path)
		res = append(res, temp)
		return
		// res = append(res, path)
		// return -------------------------------------注意！
	}

	for i := start; i <= n; i++ {
//		可优化项：
// 		剪枝，优化搜索
//		if n-i+1 < k-len(path) {
//			break
//		}
		path = append(path, i)
		dfs(i+1, n, k)
		path = path[:len(path)-1]
	}
}

注意！

情况一

1
2
3
4
5
		temp := make([]int, k)
		copy(temp, path)
		res = append(res, temp)
		return
// output : [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

情况二

1
2
3
		res = append(res, path)
		return
// output : [[1,4],[1,4],[1,4]..]

这两段代码如果没有背景条件那么运行的结果应该是相仿的，但是如果在本题的条件下确不相同

那么为什么第二种情况出来的结果都是一样的呢

当你执行 res = append(res, path) 时，实际上是将 path 的引用加入到 res 中。这意味着无论 path 后续如何变化，
res 中加入的元素都会随之改变，因为它们共享相同的底层数组。

因此，现在应该会对append，引用类型，slice有了更好的理解。

组合总和|||#

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

这道题跟上面那道题一毛一样，直接上代码

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
var (
	path  []int
	res [][]int
)
func combinationSum3(k int, n int)[][]int{
	path , res = make([]int,0) , make([][]int,0)
	backtrack(1,k,n)
	return res
}

func backtrack(start int, k int, n int){
	if len(path)==k && n==0{
		temp := make([]int,k)
		copy(temp,path)
		res = append(res,temp)
		return
	}
	for i:=start; i<10;i++{
        // 剪枝
        if n-start<0 ||len(path)>k {
            break
        }
		// 处理结果
		path = append(path,i)
		// 递归
		backtrack(i+1,k,n-i)
		path = path[:len(path)-1]
	}
	return
}

电话号码的字母组合#

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

本来想要构造两层循环+递归来做的，然后是错的，看了答案写了这个，其实我现在还是有点没懂他的逻辑，但是我debug看懂了，导致我现在有点懂了，所以懂了没有，我也不知道，算了体育课上完，我好累啊，就当写过了吧，明天见。

tips: 大体思路跟上面两题相同

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
var(
	m    []string
	path []byte
	res  []string
)

func letterCombinations(digit string) []string {
	m = []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	path, res = make([]byte, 0), make([]string, 0)
	if digit == "" {
		return res
	}
	dfs(digit, 0)
	return res
}

func dfs(digit string, start int) {
	if len(path) == len(digit) {
		res = append(res, string(path))
		return
	}
	num := int(digit[start] - '0')
	str := m[num-2]
	for i := 0; i < len(str); i++ {
		path = append(path, str[i])
		dfs(digit, start+1)
		path = path[:len(path)-1]
	}
	return
}

组合总和#

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func combinationSum(candidates []int, target int) [][]int {
	path , res := make([]int , 0) , make([][]int, 0)
	var dfs func(target, index int, path []int)
	dfs = func(target, index int, path []int) {
		if target == 0 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			return
		}
		for i := index; i < len(candidates); i++ {
			path = append(path, candidates[i])
			if target-candidates[i] >= 0 {
				dfs(target-candidates[i], i, path)
			}
			path = path[:len(path)-1]
		}
	}
	dfs(target, 0, path)
	return res
}

组合总和||#

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

这里需要注意的是：

树枝去重 和 树层去重

  1. 什么是树枝去重
  2. 什么是树层去重

其实很好理解，每一次递归就是向下遍历（树枝），而每次递归的for循环就是向广度遍历（树层），这道题的重点是树层遍历，因此要改的代码在for循环之中

最后就是去重判定条件了，就是排序，不能使用相同的元素，然后就ok了

==i != start==这个只是一个边界条件而已，为的是让后面的条件不越界，当i=0的时候

欧克，明天见。

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
var (
	res [][]int
	path  []int
)
func combinationSum2(candidates []int, target int) [][]int {
	res, path = make([][]int, 0), make([]int, 0, len(candidates))
	sort.Ints(candidates)   // 排序，为剪枝做准备
	dfs(candidates, 0, target)
	return res
}

func dfs(candidates []int, start int, target int) {
	if target == 0 {   // target 不断减小，如果为0说明达到了目标值
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		return
	}
	for i := start; i < len(candidates); i++ {
		if candidates[i] > target {  // 剪枝，提前返回
			break
		}
		// i != start 限制了这不对深度遍历到达的此值去重
		if i != start && candidates[i] == candidates[i-1] { // 去重
			continue
		}
		path = append(path, candidates[i])
		dfs(candidates, i+1, target - candidates[i])
		path = path[:len(path) - 1]
	}
}

切割#

分割回文串#

给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

1
2
输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

这道题的重点就是看示例，其实这道题的做法跟其他题目是一样的，但是你会发现他的输出有点怪，正常来说我们的输出就是所有的数字都是在同一个数组里面，那么==var res []string==,而现在res的类型是上述的切片，就这样你知道你任务是啥了—分组

那么怎么分组呐？

==start == len(s)==

ok ，整道题就此完结

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
var (
    path []string  // 放已经回文的子串
    res  [][]string
)
func partition(s string) [][]string {
    path, res = make([]string, 0), make([][]string, 0)
    dfs(s, 0)
    return res
}

func dfs(s string, start int) {
    if start == len(s) { // 如果起始位置等于s的大小，说明已经找到了一组分割方案了
        tmp := make([]string, len(path))
        copy(tmp, path)
        res = append(res, tmp)
        return 
    }
    for i := start; i < len(s); i++ {
        str := s[start : i+1]
        if isPalindrome(str) {   // 是回文子串
            path = append(path, str)
            dfs(s, i+1)         // 寻找i+1为起始位置的子串
            path = path[:len(path)-1]  // 回溯过程，弹出本次已经添加的子串
        }
    }
}

func isPalindrome(s string) bool {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}

复原IP地址#

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

这是一道切割问题，其实上一道题目也是切割问题，但是我好像把他当作了组合问题就写完了，这道题我是真不会了。

简单说一下思路，切割和组合的最大区别就是，切割的path是一段，而组合的path是一个值，这就是最大区别，因此path常常需要用slice来表示，最后通过题目的限定条件，判断广度遍历，深度遍历的条件即可

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
var (
    path []string
    res  []string
)
func restoreIpAddresses(s string) []string {
    path, res = make([]string, 0, len(s)), make([]string, 0)
    dfs(s, 0)
    return res
}
func dfs(s string, start int) {  
    if len(path) == 4 {    // 够四段后就不再继续往下递归
        if start == len(s) {      
            str := strings.Join(path, ".")
            res = append(res, str)
        }
        return 
    }
    for i := start; i < len(s); i++ {
        if i != start && s[start] == '0' { // 含有前导 0，无效
            break
        }
        str := s[start : i+1]
        num, _ := strconv.Atoi(str)
        if num >= 0 && num <= 255 {
            path = append(path, str)  // 符合条件的就进入下一层
            dfs(s, i+1)
            path = path[:len(path) - 1]
        } else {   // 如果不满足条件，再往后也不可能满足条件，直接退出
            break
        }
    }
}

子集#

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

想要理解这道题，不如直接画个图

以**[123]**为例子

水平表示树层，垂直表示树枝，从而可以看出这种划分是没有重复的

1 2 3
12 23
123

错误的划分（我一开始的划分）

会有重复，并且代码不好写，至于为什么我会这么划分，好吧全部都是上面一题的“段”的影响………….

1 12 123
2 / 3 3
23 /

最后，我感觉我写回溯还是太呆板了，重点是树枝和树层是怎么遍历的，有什么条件，如果没有条件也不需要写if，回溯中最重要的只有递归加回溯是必要的，其他都是灵活的

欧克，明天见。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var (
	path []int
	res  [][]int
)

func subsets(nums []int) [][]int {
	path, res = make([]int, 0), make([][]int,0)
	dfs(nums, 0)
	return res
}

func dfs(nums []int, start int) {
	tmp := make([]int,len(path))
	copy(tmp, path)
	res = append(res, tmp)

	for i := start; i < len(nums); i++ {
		path = append(path, nums[i])
		dfs(nums, i+1)
		path = path[:len(path)-1]
	}
}

非递减子序列#

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

这道题两个点

  1. 非递减
  2. 去重
  3. 还有一个隐含的点，数组原来排序状态不变，因此不能用**组合总和||**的思路来做这道题

不如替换一下，非递减无非就是 if 判断（注意控制数组越界问题）

去重，不如直接交给hash来解决

代码

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
var (
	path []int
	res  [][]int
)

// 不能改变原数组的排序状态

func findSubsequences(nums []int) [][]int {
	path, res = []int{}, [][]int{}
	dfs(nums, 0)
	return res
}

func dfs(nums []int, start int) {
	if len(path) >= 2 {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
	}

	used := make(map[int]bool, len(nums))
	for i := start; i < len(nums); i++ {
		if used[nums[i]] {
			continue
		}
		if len(path) > 0 || nums[i] >= path[len(path)-1] {
			path = append(path, nums[i])
			used[nums[i]] = true
			dfs(nums, i+1)
			path = path[:len(path)-1]
		}
	}
}

做完这道题，我不禁对原先我对树枝和树层的理解产生了怀疑，原先觉得for循环中就是树层，但是这道题明明需要==Len(path)>2==的条件，按道理来说应该是树枝的方向，所以具体判断条件应该在if中，那为什么正确答案还是在for中呐，唉，

不如直接上实践一下

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
// 样例代码， 输入 [4 6 7 7]
var (
	path []int
	res  [][]int
)

func findSubsequences(nums []int) [][]int {
	path, res = []int{}, [][]int{}
	dfs(nums, 0)
	return res
}

func dfs(nums []int, start int) {
	if len(path) > 0 {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
	}

	for i := start; i < len(nums); i++ {
		path = append(path, nums[i])
		dfs(nums, i+1)
		path = path[:len(path)-1]
	}

	return
}

// output:
//  [[4] [4 6] [4 6 7] [4 6 7 7] [4 6 7] [4 7] [4 7 7] [4 7] [6] [6 7] [6 7 7] [6 7] [7] [7 7] [7]]

从这个答案可以知道，递归的顺序是，先随着树枝遍历到底，在沿着树层进行遍历，等树层遍历完后，回溯到上一个树枝节点进行相应的操作，然后再看代码本身，我觉得if,for其实没有什么区别，不如直接把他看成是单层递归中的操作，而递归中的操作归根到底都是某个节点的，不如思考一下怎么不越界和遍历的顺序

暂时是这么理解的，欧克，今天就写一题了，拜拜

子集||#

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]
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
var (
	res  [][]int
	path []int
)


func subsetsWithDup(nums []int) [][]int {
	path, res = make([]int, 0), make([][]int, 0)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	dfs(0, nums)
	return res
}

// 树层去重
func dfs(start int, nums []int) {
	if start > len(nums) {
		return
	}

	temp := make([]int, len(path))
	copy(temp, path)
	res = append(res, temp)

	for i := start; i < len(nums); i++ {
		if i > start && nums[i] == nums[i-1] {
			continue
		}
		path = append(path, nums[i])
		dfs(i+1, nums)
		path = path[:len(path)-1]
	}

}

这里是树枝和树层的遍历的去重，仔细思考一下如何去重….

考虑一下整个回溯过程，哪个代码是树枝遍历过程，哪个代码是树层遍历过程，题目就会了（我的解法比代码随想录的简单哈哈哈）

全排列#

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路

一开始看这道题的时候，我就直接用组合的方法写了，然后发现有问题

后来发现问题出在 ==start== 上面，为什么呐，不如重新理解一下 排列 和 组合

用 【1 2 3】举例

组合：先取1，后取2/3，再取3/2；再取2，但是你只能取3，因为组合是没有顺序之分的

排列：先取1，后取2/3，再取3/2；再取2，但排列中你还可以取1/3，再取3/1，是顺序区分的

而start正是表示出是否重复取的关键，但dfs(nums,start+1)传入以后会发现后面的每次递归的start都会越来越大，导致如果你一开始取2，后面取的数就不可能是1，因此start应该为0，变成==for i:=start ; i<len(nums) ; i++{==，但是现在问题又来了，你会发现如果遍历123三个数就会出现 [1,1,1],[2,2,2],[3,3,3]这些重复的数字，所以需要去重，就需要使用state[]数组来记录

欧克，大体思路就是这样

代码

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
var (
	path []int
	res  [][]int
	state []bool
)

func permute(nums []int) [][]int {
	path, res, state = make([]int, 0), make([][]int, 0, len(nums)), make([]bool,len(nums))
	dfs(nums, 0)
	return res
}

func dfs(nums []int, cur int) {
	if cur == len(nums) {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
	}

	for i := 0; i < len(nums); i++ {
		if !state[i]{
			path = append(path, nums[i])
			state[i]= true 
			dfs(nums, cur+1)
			state[i] = false
			path = path[:len(path)-1]
		}
	}

	return
}

全排列||#

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

这道题就是全排列+去重的组合，具体怎么做前面的题目都有类似的我就不赘述了

代码

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
var (
	path  []int
	res   [][]int
	state []bool
)

func permuteUnique(nums []int) [][]int {
	path, res, state = make([]int, 0), make([][]int, 0, len(nums)), make([]bool, len(nums))
	sort.Ints(nums)
	dfs(nums, 0)
	return res
}

func dfs(nums []int, cur int) {
	if cur == len(nums) {
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)
	}

	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] && !state[i-1] {
			continue
		}
		if !state[i]{
			path = append(path, nums[i])
			state[i] = true
			dfs(nums, cur+1)
			path = path[:len(path)-1]
			state[i] = false
		}
	}
}

重新安排行程#

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

img

1
2
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

思路：

首先提醒： 这道题是困难题

但是思路其实很简单，这道题的关键在于如何判断==tickets==都游过了

算了其实我也不知道这道题有什么难的，唯一的难点就是

他特么就是内存超出，唉

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
// 自认为的写法： 但内存超出
var (
	path []string
	res  [][]string
)

func findItinerary(tickets [][]string) []string {
	path, res = make([]string, 0), make([][]string, 0, len(tickets))
	dfs("JFK", tickets)
	sort.Slice(res, func(i, j int) bool {
		for k := range res[i] {
			if res[i][k] != res[j][k] {
				return res[i][k] < res[j][k]
			}
		}
		return true
	})

	return res[0]
}

func dfs(cur string, tickets [][]string) {
	if len(path) == 0 {
		path = append(path, cur)
	}

	if len(tickets) == 0 {
		tmp := make([]string, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		return
	}

	for i := 0; i < len(tickets); i++ {
		if tickets[i][0] == cur {
			path = append(path, tickets[i][1])
			tmp := make([][]string, len(tickets)-1)
			copy(tmp[:i], tickets[:i])
			copy(tmp[i:], tickets[i+1:])
			dfs(tickets[i][1], tmp)
			path = path[:len(path)-1]
		}
	}

	return
}

代码随想录：

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
type pair struct {
	target  string
	visited bool
}
type pairs []*pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}
func (p pairs) Less(i, j int) bool {
	return p[i].target < p[j].target
}

func findItinerary(tickets [][]string) []string {
	result := []string{}
	// map[出发机场] pair{目的地,是否被访问过}
	targets := make(map[string]pairs)
	for _, ticket := range tickets {
		if targets[ticket[0]] == nil {
			targets[ticket[0]] = make(pairs, 0)
		}
		targets[ticket[0]] = append(targets[ticket[0]], &pair{target: ticket[1], visited: false})
	}
	for k, _ := range targets {
		sort.Sort(targets[k])
	}
	result = append(result, "JFK")
	var backtracking func() bool
	backtracking = func() bool {
		if len(tickets)+1 == len(result) {
			return true
		}
		// 取出起飞航班对应的目的地
		for _, pair := range targets[result[len(result)-1]] {
			if pair.visited == false {
				result = append(result, pair.target)
				pair.visited = true
				if backtracking() {
					return true
				}
				result = result[:len(result)-1]
				pair.visited = false
			}
		}
		return false
	}

	backtracking()

	return result
}

不想解释这个代码，因为我觉得我就是对的，真尼玛

N皇后#

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

N 皇后

个人觉得到了困难难度，其实就i没有讲解思路的必要了，都是中等初级难度的叠加

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
func solveNQueens(n int) [][]string {
    var res [][]string
	chessboard := make([][]string, n)
	for i := 0; i < n; i++ {
		chessboard[i] = make([]string, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			chessboard[i][j] = "."
		}
	}
	var backtrack func(int)
	backtrack = func(row int) {
		if row == n {
			temp := make([]string, n)
			for i, rowStr := range chessboard {
				temp[i] = strings.Join(rowStr, "")
			}
			res = append(res, temp)
			return
		}
		for i := 0; i < n; i++ {
			if isValid(n, row, i, chessboard) {
				chessboard[row][i] = "Q"
				backtrack(row + 1)
				chessboard[row][i] = "."
			}
		}
	}
	backtrack(0)
	return res
}

func isValid(n, row, col int, chessboard [][]string) bool {
	for i := 0; i < row; i++ {
		if chessboard[i][col] == "Q" {
			return false
		}
	}
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if chessboard[i][j] == "Q" {
			return false
		}
	}
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if chessboard[i][j] == "Q" {
			return false
		}
	}
	return true
}

解数独#

解不出来，自行看官方解答吧

37. 解数独 - 力扣（LeetCode）

总结#

  1. 回溯有模板，很多题目虽然是中等难度，但是其实不难
  2. 回溯树枝，树层
  3. 有点累，懒得总结了，多练吧

明天 贪心 启动！