Hollis的个人博客
Hollis的个人博客

代码随想录：回溯算法

Hollis Hollis 收录于 Algorithm 和 代码随想录
  约 6300 字 预计阅读 13 分钟  - 次阅读   - 条评论  

组合

77. 组合

1
2
3
4
5
6
7
8
9

func main() {
    n := 4
    k := 2
    r := combine(n, k)
    fmt.Println(r) // [[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]]
}
func combine(n int, k int) [][]int {
	// ......
}
答案

使用 递归 + 回溯 的算法。

在树的第 1 层，选择一个 start 作为本次递归的起始值，start 从 1 开始，到 n 结束。

在下层递归中，start 从上层的后一个数开始（这样就保证了得到的组合不会有重复的情况）。

将每层选择的元素组合成一个一维数组 arr，如果 arr 的长度为 2，则可以终止递归，向上回溯了。

 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

func combine(n int, k int) [][]int {
    if k > n { // 区间不合法
       return nil
    }
    arr := make([]int, 0)
    result := make([][]int, 0)
    if k == n {
       for i := 1; i <= n; i++ {
          arr = append(arr, i)
       }
       return [][]int{arr}
    }
    var backTracking func(start, n, k int)
    backTracking = func(start, n, k int) {
       if len(arr) == k { // 递归出口
          // 注意这里将一维切片添加到二维切片时，如果后面对一维切片进行了修改，也会导致二维切片值的变化（共享相同的引用）
          // 所以这里我们要拷贝arr的值副本，再将副本添加到result中
          temp := make([]int, k)
          copy(temp, arr)
          result = append(result, temp)
          return
       }
       for i := start; i <= n; i++ {
          // 剪枝：如果总元素不足k个，直接返回
          if n-i+1 < k-len(arr) { // k-len(arr)表示还需要的元素个数，n-i+1表示还能提供的元素个数
             return
          }
          arr = append(arr, i)    // 添加本层元素到arr中
          backTracking(i+1, n, k) // 递归调用
          arr = arr[:len(arr)-1]  // 回溯，去掉最后一个元素
       }
    }
    backTracking(1, n, k)
    return result
}

组合总和III

216. 组合总和 III

1
2
3
4
5
6
7
8
9

func main() {
    k := 3
    n := 9
    r := combinationSum3(k, n)
    fmt.Println(r) // [[1,2,6], [1,3,5], [2,3,4]]
}
func combinationSum3(k int, n int) [][]int {
    // ......
}
答案

本题和上面一个题差不多，也是本层递归选定一个数，下一层递归又选定一个数。

 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

func combinationSum3(k int, n int) [][]int {
    arr := make([]int, 0)
    res := make([][]int, 0)
    sum := 0
    var backtracking func(start, k, n int)
    backtracking = func(start, k, n int) {
       // 递归出口：arr中的元素个数等于k / sum大于n
       if len(arr) == k {
          if sum == n {
             temp := make([]int, k)
             copy(temp, arr)
             res = append(res, temp)
          }
          return
       }
       if sum > n {
          return
       }
       for i := start; i <= 9; i++ {
          // 剪枝：总个数不足k个
          if 9-i+1 < k-len(arr) { // k-len(arr)表示需要的个数，9-i+1表示还能提供的个数
             return
          }
          // 剪枝：sum大于n
          if sum > n {
             return
          }
          arr = append(arr, i)
          sum += i
          backtracking(i+1, k, n)
          arr = arr[:len(arr)-1] // 回溯
          sum -= i
       }
    }
    backtracking(1, k, n)
    return res
}

电话号码的字母组合

17. 电话号码的字母组合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func main() {
    digits := "23"
    r := letterCombinations(digits)
    fmt.Println(r) // [ad ae af bd be bf cd ce cf]
}
func letterCombinations(digits string) []string {
	mapping := [10]string{
       0: "",
       1: "",
       2: "abc",
       3: "def",
       4: "ghi",
       5: "jkl",
       6: "mno",
       7: "pqrs",
       8: "tuv",
       9: "wxyz",
    }
    // ......
}
答案

先将数字和其对应的字符集合做映射，可以用 map 或数组，这里就采用数组。

然后遍历 digits，digits[0] 对应的字符集合做递归的第 1 层。

每层递归就将 digits 的下标后移一位，我们可以定义一个 index 表示当前遍历到 digits 的下标。

 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

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
       return nil
    }
    res := make([]string, 0)
    mapping := [10]string{
       0: "",
       1: "",
       2: "abc",
       3: "def",
       4: "ghi",
       5: "jkl",
       6: "mno",
       7: "pqrs",
       8: "tuv",
       9: "wxyz",
    }
    if len(digits) == 1 {
       num, _ := strconv.Atoi(digits)
       for i := 0; i < len(mapping[num]); i++ {
          res = append(res, string(mapping[num][i]))
       }
       return res
    }
    arr := make([]byte, 0) // 保存已经遍历过的字符集
    var backtracking func(digits string, index int)
    backtracking = func(digits string, index int) {
       if index == len(digits) {
          temp := string(arr)
          res = append(res, temp)
          return
       }
       // 将byte类型的数字转换为int类型，先减去字符'0'，再转换为int类型
       // 如果直接强制转换，得到的是字符的ascii码值
       // 也不能使用 strconv.Atoi() 函数，因为该函数只能接收string类型的变量
       digit := int(digits[index] - '0') // 获取到当前遍历到的下标
       stringLetter := mapping[digit]    // 获取到当前下标对应的字符集合
       for i := 0; i < len(stringLetter); i++ {
          arr = append(arr, stringLetter[i])
          backtracking(digits, index+1) // 递归（第二个参数为index+1，表示进入下一层递归，起始位置加1）
          arr = arr[:len(arr)-1]        // 回溯
       }
    }
    backtracking(digits, 0)
    return res
}

组合总和

39. 组合总和

1
2
3
4
5
6
7
8
9

func main() {
    candidates := []int{2, 3, 5, 4}
    target := 8
    r := combinationSum(candidates, target)
    fmt.Println(r) // [[2 2 2 2] [2 2 4] [2 3 3] [3 5] [4 4]]
}
func combinationSum(candidates []int, target int) [][]int {
    // ......
}
答案

本题和 组合 的题目差不多，但需要注意的是，数组中的元素是可以重复使用的。

所以在下次递归时，传入的参数是 i 而不是 i+1。

为了防止出现重复的结果集，我们也要使用 startIndex 参数来控制递归的开始位置。

 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

func combinationSum(candidates []int, target int) [][]int {
    res := make([][]int, 0)
    arr := make([]int, 0)
    sum := 0
    slices.Sort(candidates) // 配合剪枝策略使用（在求和问题中，排序之后加剪枝是常见的套路！）
    var backtracking func(candidates []int, target, startIndex int)
    backtracking = func(candidates []int, target, startIndex int) {
       // 递归出口
       if sum == target {
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          return
       }
       for i := startIndex; i < len(candidates); i++ {
          // 剪枝策略：先对candidates数组排序，再判断当前的sum是否大于target，如果是，则直接返回
          if sum+candidates[i] > target {
             return
          }
          sum += candidates[i]
          arr = append(arr, candidates[i])
          backtracking(candidates, target, i) // 注意：这里的最后一个参数是i，而不是i+1
          sum -= candidates[i]                // 回溯
          arr = arr[:len(arr)-1]
       }
    }
    backtracking(candidates, target, 0)
    return res
}

组合总和II

40. 组合总和 II

1
2
3
4
5
6
7
8
9

func main() {
    candidates := []int{10, 1, 2, 7, 6, 1, 5}
    target := 8
    r := combinationSum2(candidates, target)
    fmt.Println(r) // [[1 1 6] [1 2 5] [1 7] [2 6]]
}
func combinationSum2(candidates []int, target int) [][]int {
    // ......
}
答案

本题的和 组合 不同的地方在于，候选数组 candidates 中存在相同的元素。

我们使用 arr 数组保存遍历过的元素，在 arr 中，我们可以取相同的元素，但 res 中不能有重复的组合 如何去重呢？

这涉及到 树枝去重 和 树层去重。

树枝去重就是对 arr 选择的元素去重，显然，本题允许 arr 中存在重复值，所以不能对树枝进行去重；

树层去重就是某次遍历中出现某个元素时，在后面的遍历中又出现了相同的元素，那么我们就应该跳过后面本次遍历过程，因为前面的遍历已经包含了后面遍历的过程。

具体实现：先对候选数组排序，然后使用 used 数组来标记每个下标的元素是否已经用过了；

如果 candidates[i] 和 candidates[i-1] 相等（出现了重复元素），如果 used[i-1]==0（说明是树层重复），那么就应该跳过本次递归。

used[i-1]==1 是树枝重复，在后面的遍历中，会回溯，将 used[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
32
33
34
35
36

func combinationSum2(candidates []int, target int) [][]int {
    if len(candidates) == 0 {
       return nil
    }
    arr := make([]int, 0)
    res := make([][]int, 0)
    used := make([]bool, len(candidates))
    sum := 0
    slices.Sort(candidates)
    var backtracking func(candidates []int, target, start int)
    backtracking = func(candidates []int, target, start int) {
       if sum == target {
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          return
       }
       for i := start; i < len(candidates); i++ {
          if sum+candidates[i] > target { // 剪枝
             return
          }
          if i > 0 && candidates[i-1] == candidates[i] && !used[i-1] { // 树层重复
             continue
          }
          sum += candidates[i]
          used[i] = true
          arr = append(arr, candidates[i])
          backtracking(candidates, target, i+1) // 递归，起始位置为i+1
          sum -= candidates[i]                  // 回溯
          used[i] = false
          arr = arr[:len(arr)-1]
       }
    }
    backtracking(candidates, target, 0)
    return res
}

分割回文串

131. 分割回文串

1
2
3
4
5
6
7
8

func main() {
    s := "aab"
    r := partition(s)
    fmt.Println(r) // [[a a b] [aa b]]
}
func partition(s string) [][]string {
    // ......
}
答案

本题和 组合 问题差不多，都是每层递归，选择元素的位置往后移动 1 位我们使用 start 表示我们本次切割的位置。

在每层递归遍历中，对 start 后面的字符串进行切割，判断是否是回文字符串，切割的区间就是 start 到 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

func partition(s string) [][]string {
    arr := make([]string, 0) // 保存切割过的字符串
    res := make([][]string, 0)
    var backtracking func(s string, start int)
    backtracking = func(s string, start int) {
       // 确定终止条件，start表示的就是切割线，当切割线到字符串s的最末尾的时候，就应该结束递归过程了，
       // 并将arr中的结果保存到res中
       if start == len(s) {
          temp := make([]string, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          return
       }
       for i := start; i < len(s); i++ {
          if isPalindrome(s, start, i) { // 是回文字符串，就加入到arr中，否则跳过本次递归
             arr = append(arr, s[start:i+1])
             backtracking(s, i+1) // 下层递归从i+1位置开始（切割位置每次后移一位）
             arr = arr[:len(arr)-1]
          }
       }
    }
    backtracking(s, 0)
    return res
}
func isPalindrome(s string, left, right int) bool {
    for left < right {
       if s[left] != s[right] {
          return false
       }
       left++
       right--
    }
    return true
}

复原IP地址

93. 复原 IP 地址

1
2
3
4
5
6
7
8

func main() {
    s := "25525511135"
    r := restoreIpAddresses(s)
    fmt.Println(r) // ["255.255.11.135","255.255.111.35"]
}
func restoreIpAddresses(s string) []string {
    // ......
}
答案

本题和 分割回文串 差不多，也是每层递归，截取字符串的起始位置 start 往后移一位。

每层遍历中，遍历 start 往后的字符串，判断 start 到 i（左闭右闭）区间的字符串是否合法。

如果不合法，直接跳过本次递归；如果合法，将区间内的字符串加入到 arr 中。

我们还需要统计现在已经添加分割点 ( . ) 的个数 dotCount，如果大于等于三个，退出本次递归（递归出口）。

当 dotCount 等于 3 时，判断后面剩下的字符串是否符合 ip 的要求，如果不合法，直接 return，如果合法，将 arr 和后面的字符串一起加入到 res 中。

 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

func restoreIpAddresses(s string) []string {
	arr := make([]string, 0)
	arrStr := ""
	res := make([]string, 0)
	dotCount := 0
	var backtracking func(s string, start int)
	backtracking = func(s string, start int) {
		arrStr = ""
		if dotCount == 3 {
			if isValid(s, start, len(s)-1) {
				//for i := 0; i < len(arr); i++ { // 将arr数组转换为加点的ip字符串
				//	if i == len(arr)-1 {
				//		arrStr += arr[i]
				//	} else {
				//		arrStr += arr[i] + "."
				//	}
				//}
				arrStr = strings.Join(arr, ".") // 上面的代码可以用这行代码来替换
				arrStr += "." + s[start:]
				res = append(res, arrStr)
			}
			return
		}
		for i := start; i < len(s); i++ {
			if isValid(s, start, i) {
				arr = append(arr, s[start:i+1])
				dotCount++
				backtracking(s, i+1) // 下层递归从i+1位置开始
				arr = arr[:len(arr)-1]
				dotCount--
			}
		}
	}
	backtracking(s, 0)
	return res
}
// 判断字符串 s 在 left 到 right 区间（左闭右闭）上的子字符串是否合法
func isValid(s string, left, right int) bool {
	if right-left > 2 {  // 超过3个元素
		return false
	}
	if right-left > 0 { // 至少2个元素
		if s[left] == '0' { // 存在前缀0
			return false
		}
	}
	str := s[left : right+1]
	num, err := strconv.Atoi(str)
	if err != nil {
		return false
	}
	if num < 0 || num > 255 {
		return false
	}
	return true
}

子集

78. 子集

1
2
3
4
5
6
7
8

func main() {
    nums := []int{1, 2, 3}
    r := subsets(nums)
    fmt.Println(r) // [[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]
}
func subsets(nums []int) [][]int {
	// ......
}
答案

本题和 组合 差不多，也是每层递归选择一个元素，start 表示本次递归的起始位置。

但本题和 组合 问题不一样的地方在于，本题的结果分布在树的各个结点，而不是叶子结点，所以我们不能再终止条件（叶子结点）处收获结果，而应该在每层递归时将结果添加到 res 中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func subsets(nums []int) [][]int {
    arr := make([]int, 0)
    res := make([][]int, 1)
    res[0] = []int{} // 先将空集加入到res中
    var backtracking func(nums []int, start int)
    backtracking = func(nums []int, start int) {
       if start == len(nums) {
          //temp := make([]int, len(arr))  // 不再是在叶子结点处收获结果
          //copy(temp, arr)
          //res = append(res, temp)
          return
       }
       for i := start; i < len(nums); i++ {
          arr = append(arr, nums[i])
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          backtracking(nums, i+1)
          arr = arr[:len(arr)-1]
       }
    }
    backtracking(nums, 0)
    return res
}

子集II

90. 子集 II

1
2
3
4
5
6
7
8

func main() {
    nums := []int{1, 2, 2}
    r := subsetsWithDup(nums)
    fmt.Println(r) // [[] [1] [1 2] [1 2 2] [2] [2 2]]
}
func subsetsWithDup(nums []int) [][]int {
	// ......
}
答案

本题和 组合总和II 差不多，都是候选数组中存在重复元素，但最后的结果集不能有重复的组合。

我们需要进行树层去重，使用 used 数组标识某个位置的元素是否已经使用过；

如果没有使用过（说明是回溯之后的，也就是树层出现了重复值），且存在和前一个值相同的情况，那么就应该去重（直接跳过本次递归）。

 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

func main() {
    nums := []int{1, 2, 2}
    r := subsetsWithDup(nums)
    fmt.Println(r)
}
func subsetsWithDup(nums []int) [][]int {
    arr := make([]int, 0)
    res := make([][]int, 1)
    res[0] = []int{}
    used := make([]bool, len(nums))
    slices.Sort(nums)
    var backtracking func(nums []int, start int)
    backtracking = func(nums []int, start int) {
       if start == len(nums) { // 递归终止条件
          return
       }
       for i := start; i < len(nums); i++ {
          if i > 0 && nums[i-1] == nums[i] && !used[i-1] { // 树层去重
             continue
          }
          arr = append(arr, nums[i])
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          used[i] = true
          backtracking(nums, i+1)
          arr = arr[:len(arr)-1]
          used[i] = false
       }
    }
    backtracking(nums, 0)
    return res
}

非递减子序列

491. 非递减子序列

1
2
3
4
5
6
7
8

func main() {
    nums := []int{1, 2, 3, 1, 1}
	r := findSubsequences(nums)
	fmt.Println(r) // [[1 2] [1 2 3] [1 3] [1 1] [1 1 1] [2 3]]
}
func findSubsequences(nums []int) [][]int {
    // ......
}
答案

本题也需要树层去重，由于是子序列，所以我们不能对原数组进行排序。

对树层去重的逻辑是判断这个是否之前出现过（需要用到 set），如果出现过的话，那么就可以进行树层去重。

为了达到树层去重的效果，需要在递归中定义 set，而不是使用全局变量。 因为该 set 应该只对本层递归有效（在 for 循环之前定义），而不是全局有效，如果改成全局变量，无法判断是树层重复还是树枝重复。

我们需要判断当前遍历到的数是否大于等于 arr 的最后一个数，如果是（非递减），则将该数加入到 arr 中。

 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

func findSubsequences(nums []int) [][]int {
    arr := make([]int, 0)
    res := make([][]int, 0)
    var backtracking func(nums []int, start int)
    backtracking = func(nums []int, start int) {
       if len(arr) >= 2 { // 遍历中，将符合条件的结果添加到res中
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
       }
       usedNum := make(map[int]bool, len(nums)) // 存放出现过的元素
       // 将usedNum定义在backtracking函数内部可以确保每次递归调用都会使用一个新的、独立的usedNum变量
       // 将usedNum定义在backtracking函数内部，是为了让每层递归时，不要取重复值
       for i := start; i < len(nums); i++ {
          // 树层去重
          if usedNum[nums[i]] {
             continue
          }
          if len(arr) == 0 || nums[i] >= arr[len(arr)-1] {
             arr = append(arr, nums[i])
             usedNum[nums[i]] = true
             backtracking(nums, i+1)
             arr = arr[:len(arr)-1]
             //usedNum[nums[i]] = false
             // 由于每层递归的usedNum是彼此独立的，所以不能使用全局变量usedNum，来设置usedNum的值
          }
       }
    }
    backtracking(nums, 0)
    return res
}

全排列

46. 全排列

1
2
3
4
5
6
7
8

func main() {
    nums := []int{1, 2, 3}
    r := permute(nums)
    fmt.Println(r) // [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
}
func permute(nums []int) [][]int {
    // ......
}
答案

排列问题和 组合 问题不同的地方在于，在递归的过程中，排列问题可以取之前取过的元素，但同样的，每个元素也不能重复使用。

我们可以定义一个 used 数组，来标记递归中已经使用过的元素下标。

 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

func permute(nums []int) [][]int {
    arr := make([]int, 0)
    res := make([][]int, 0)
    used := make([]bool, len(nums))
    var backtracking func(nums []int)
    backtracking = func(nums []int) {
       if len(arr) == len(nums) { // arr中元素个数和nums相同时，返回
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          return
       }
       for i := 0; i < len(nums); i++ { // i从0开始
          if used[i] {  // 跳过已经使用的元素
             continue
          }
          used[i] = true // used数组用来标记本次递归中使用过的元素位置
          arr = append(arr, nums[i])
          backtracking(nums)
          used[i] = false
          arr = arr[:len(arr)-1]
       }
    }
    backtracking(nums)
    return res
}

全排列II

47. 全排列 II

1
2
3
4
5
6
7
8

func main() {
    nums := []int{1, 1, 2}
    r := permuteUnique(nums)
    fmt.Println(r) // [[1 1 2] [1 2 1] [2 1 1]]
}
func permuteUnique(nums []int) [][]int {
    // ......
}
答案

本题需要先对 nums 排序，然后树层去重。

 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

func permuteUnique(nums []int) [][]int { 
    arr := make([]int, 0)
    res := make([][]int, 0)
    used := make([]bool, len(nums))
    sort.Ints(nums)
    var backtracking func(nums []int)
    backtracking = func(nums []int) {
       if len(arr) == len(nums) {
          temp := make([]int, len(arr))
          copy(temp, arr)
          res = append(res, temp)
          return
       }
       for i := 0; i < len(nums); i++ {
          // 去掉递归中已经使用过的元素，并进行树层去重
          if used[i] || (i > 0 && nums[i-1] == nums[i] && !used[i-1]) {
             continue
          }
          used[i] = true
          arr = append(arr, nums[i])
          backtracking(nums)
          arr = arr[:len(arr)-1]
          used[i] = false
       }
    }
    backtracking(nums)
    return res
}

N皇后(困难)

51. N 皇后

1
2
3
4
5
6
7
8

func main() {
    n := 4
    r := solveNQueens(n)
    fmt.Println(r) // [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
}
func solveNQueens(n int) [][]string {
    // ......
}
答案

本题和前面的排列、组合、分割不同的地方在于，这是一个二维数组，而不是一维数组。

我们需要定义一个二维数组 chessboard，表示棋盘。

我们可以使用 row 表示我们当前遍历到的行下标，每层递归的 row 增加 1。

当 row 等于等于 n-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
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

func solveNQueens(n int) [][]string {
    chessboard := make([][]string, n) // 棋盘
    for i := range chessboard {
       chessboard[i] = make([]string, n)
    }
    for i := 0; i < len(chessboard); i++ {
       for j := 0; j < len(chessboard); j++ {
          chessboard[i][j] = "."
       }
    }
    res := make([][]string, 0) // 最后的结果
    var backtracking func(chessboard [][]string, n, row int)
    backtracking = func(chessboard [][]string, n, row int) {
       if row == n { // 递归出口
          arr := make([]string, n) // 将棋盘的每行转换为字符串
          for i, bytes := range chessboard {
             arr[i] = strings.Join(bytes, "")
          }
          res = append(res, arr)
       }
       for i := 0; i < n; i++ { // i从0到n-1（遍历每行的每个元素）
          if isValidChessboard(chessboard, n, row, i) {
             chessboard[row][i] = "Q"
             backtracking(chessboard, n, row+1) // 每层递归，row加1
             chessboard[row][i] = "."
          }
       }
    }
    backtracking(chessboard, n, 0)
    return res
}
func isValidChessboard(chessboard [][]string, n, row int, col int) bool {
    // 检查列
    for i := 0; i < row; i++ {
       if chessboard[i][col] == "Q" {
          return false
       }
    }
    // 检查 45度角是否有皇后
    i := row - 1
    j := col - 1
    for i >= 0 && j >= 0 {
       if chessboard[i][j] == "Q" {
          return false
       }
       i--
       j--
    }
    // 检查 135度角是否有皇后
    i = row - 1
    j = col + 1
    for i >= 0 && j < n {
       if chessboard[i][j] == "Q" {
          return false
       }
       i--
       j++
    }
    return true
}

解数独(困难)

37. 解数独

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func main() {
    var board = [][]byte{
       {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
       {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
       {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
       {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
       {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
       {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
       {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
       {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
       {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
    }
    solveSudoku(board)
    for i := range board {
       fmt.Printf("%c\n", board[i])
    }
}
func solveSudoku(board [][]byte) {
    // ......
}
答案

本题和 N 皇后都是二维棋盘问题。

但不同的地方在于，N 皇后可以每层递归扫码一行数据。

而数独问题不能扫描一行，而需要扫描每个具体的棋盘位置，判断该位置能否放置指定的数字。

所以在递归函数中，需要使用两个 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func solveSudoku(board [][]byte) {
    var backtracking func(board [][]byte) bool
    backtracking = func(board [][]byte) bool {
       for i := 0; i < len(board); i++ {
          for j := 0; j < len(board); j++ {
             if board[i][j] == '.' {
                for k := '1'; k <= '9'; k++ {
                   if isValidNum(board, i, j, byte(k)) {
                      board[i][j] = byte(k)
                      if backtracking(board) { // 满足条件直接向上返回
                         return true
                      }
                      board[i][j] = '.'
                   }
                }
                return false // 9个数都尝试了，都无法满足条件，返回false
             }
          }
       }
       return true // 所有空的位置都填满了，返回true
    }
    backtracking(board)
}
// 验证插入的元素是否合法，board表示棋盘，i，j表示插入的位置，k表示插入的元素值
func isValidNum(board [][]byte, row, col int, k byte) bool {
    for i := 0; i < 9; i++ { //行
       if board[row][i] == k {
          return false
       }
    }
    for i := 0; i < 9; i++ { //列
       if board[i][col] == k {
          return false
       }
    }
    //方格
    startRow := (row / 3) * 3 // 计算当前9宫格的起始坐标
    startCol := (col / 3) * 3
    for i := startRow; i < startRow+3; i++ {
       for j := startCol; j < startCol+3; j++ {
          if board[i][j] == k {
             return false
          }
       }
    }
    return true
}
收录于 合集・代码随想录 7
更新于 2025-04-08 
CC BY-NC-SA 4.0
LeetcodeAlgorithm
返回 | 主页
0%