回溯
#LeetCode#算法#回溯 2023-12-31

回溯

回溯三问

  • 当前操作
  • 子问题
  • 下一个子问题

题目

子集型

17. 电话号码的字母组合 - 力扣（LeetCode）

78. 子集 - 力扣（LeetCode）

131. 分割回文串 - 力扣（LeetCode）

组合型

77. 组合 - 力扣（LeetCode）

216. 组合总和 III - 力扣（LeetCode）

22. 括号生成 - 力扣（LeetCode）

排列型

46. 全排列 - 力扣（LeetCode）

51. N 皇后 - 力扣（LeetCode）

52. N 皇后 II - 力扣（LeetCode）

LeetCode 17

思路

像深度优先搜索一样，递归的枚举每一个字母。

代码实现

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
var mapping = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

func letterCombinations(digits string) []string {
    var n = len(digits)
    if n == 0{
        return nil
    }

    var path = make([]byte, n)
    var dfs func(int)
    var ans []string

    dfs = func(i int){
        if i == n{
            ans = append(ans, string(path))
            return
        }

        for _, s := range mapping[digits[i] - '0']{
            path[i] = byte(s)
            dfs(i+1)
        }
    }
    dfs(0)
    return ans
}

LeetCode 78

思路

  • 当前操作：当前元素是否被选择
  • 子问题：枚举下标 > i 的元素可以构成的子集
  • 下一个子问题：枚举下标 > i + 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
func subsets(nums []int) [][]int {
    var n = len(nums)
    var path = make([]int, 0, n)
    var ans [][]int
    var dfs func(int)

    dfs = func(i int){
        if i == n{
            // 确保每一个 path 都是独立的子集
            ans = append(ans, append([]int(nil), path...))
            return
        }

        // 当前元素不选
        dfs(i + 1)

        // 当前元素选
        path = append(path, nums[i])
        dfs(i + 1)

        // 递归前啥样，递归后也要变成啥样
        path = path[:len(path) - 1] 
    }
    dfs(0)
    return ans
}

LeetCode 131

思路

将字符串分割时以逗号为界，那么：

  • 当前操作：当前逗号是否被选择
  • 子问题：枚举下标 > i 的元素可以构成的子集
  • 下一个子问题：枚举下标 > i + 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
func partition(s string) [][]string {
    var n = len(s)
    var path = make([]string, 0)
    
    var ans [][]string
    var dfs func(int, int)

    dfs = func(i int, start int){
        if i == n{
            for _, str := range path{
                if !isPalindrome(str){
                    return
                }
            }
            ans = append(ans, append([]string{}, path...))
            return
        }

        // 当前逗号不选择，最后一个 i 就没逗号了
        if i < n - 1{
            dfs(i + 1, start)
        }
        // 当前逗号选择
        path = append(path, s[start:i + 1])
        dfs(i + 1, i + 1)
        // 恢复原样
        path = path[:len(path) - 1]
    }
    dfs(0, 0)
    return ans
}

// isPalindrome 是否是回文串
func isPalindrome(s string) bool{
    var left, right = 0, len(s) - 1
    for left < right{
        if s[left] == s[right]{
            left++
            right--
            continue
        }
        return false
    }
    return true
}

LeetCode 77

思路

老方法感觉和之前的没啥不一样。

对于优化，即剪枝。设 d = n - len(path)，d 代表的就是还要选多少个数。如果 d == 0，那么当前可以记录成答案。如果 i < d，那么其实可以不用递归下去了。

代码实现

老方法：

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 combine(n int, k int) [][]int {
    var ans [][]int
    var path []int
    var dfs func(int)

    dfs = func(i int){
        if len(path) == k{
            ans = append(ans, append([]int{}, path...))        
            return
        }
        
        if i > n{
            return
        }
        
        // 当前元素不选择
        dfs(i + 1)
        // 当前元素选择
        path = append(path, i)
        dfs(i + 1)

        path = path[:len(path) - 1]
    }
    dfs(1)
    return ans
}

剪枝优化：

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
func combine(n int, k int) [][]int {
    var ans [][]int
    var path []int
    var dfs func(int)

    dfs = func(i int){
        d := k - len(path)
        if d == 0{
            ans = append(ans, append([]int{}, path...))        
            return
        }
        
        if i < d {
            return
        }
        
        // 当前元素不选择
        dfs(i - 1)
        // 当前元素选择
        path = append(path, i)
        dfs(i - 1)

        path = path[:len(path) - 1]
    }
    dfs(n)
    return ans
}

LeetCode 216

思路

剪枝太难想了……

代码实现

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 combinationSum3(k int, n int) [][]int {
    var path []int
    var ans [][]int
    var dfs func(int, int)

    dfs = func(i, sum int){
        if sum == n && len(path) == k{
            ans = append(ans, append([]int{}, path...))
            return
        }

        if i > 9 {
            return
        }

        // 不选 i
        dfs(i + 1, sum)
        // 选 i
        sum += i
        path = append(path, i)
        dfs(i + 1, sum)

        sum -= i
        path = path[:len(path) - 1]
    }
    dfs(1, 0)
    return ans
}

LeetCode 22

代码实现

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
func generateParenthesis(n int) []string {
    var m = 2 * n // 括号的个数
    var path = make([]byte, m)
    var ans []string
    var dfs func(int, int)
    // left 作为当前左括号的个数传递下去
    dfs = func(i, left int){
        if i == m{
            ans = append(ans, string(path))
            return
        }

        if left < n{
            // 当前可以是左括号
            path[i] = '('
            dfs(i + 1, left + 1)
        }

        if i - left < left{
            path[i] = ')'
            dfs(i + 1, left)
        }

    }
    dfs(0, 0)
    return ans
}

LeetCode 46

思路

排列型的答案长度是固定的，path 只能是替换而不是填充。所以在枚举时应该是当前元素是否填充，然后补齐后面元素。

代码实现

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
func permute(nums []int) [][]int {
    var n = len(nums)
    var path = make([]int, n)
    var onPath = make([]bool, n)
    var ans [][]int
    var dfs func(int)

    dfs = func(i int){
        if i == n{
            ans = append(ans, append([]int{}, path...))
            return
        }

        for j, isOnPath := range onPath{
            if !isOnPath{
                onPath[j] = true
                path[i] = nums[j]
                dfs(i + 1)
                onPath[j] = false
            }
        }
    }
    dfs(0)
    return ans
}

LeetCode 51

思路

根据题意可以得到，每一列每一行只有一个皇后放置，所以我们使用一个数组 col 来记录该列是否放置了皇后。

关于斜线，有两条规律是：

  • 如果当前 i（横坐标）+ j（纵坐标）和前面已放置的皇后的横纵坐标和相等，那么它们处于一条向右偏移的斜线上。
  • 如果当前 i（横坐标）- j（纵坐标）和前面已放置的皇后的横纵坐标差相等，那么它们处于一条向左偏移的斜线上。

将 i 定义为当前枚举的行数，然后遍历枚举 col，如果当前列没被放置，且左右斜线均无皇后，那么这是一个可以放置的位置。

按照上述思路，与 46 一样的实现，即可完成本题。

代码实现

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
func solveNQueens(n int) [][]string {
    var modelByte = make([]byte, n)
    for i := range modelByte{
        modelByte[i] = '.'
    }

    var col = make([]bool, n) // 记录哪一列已经有皇后了
    var have1 = make(map[int]bool) // 右斜线上是否有元素
    var have2 = make(map[int]bool) // 左斜线上是否有元素

    var path = make([]string, n)
    var ans [][]string
    var dfs func(int)

    dfs = func(i int){
        if i == n{
            ans = append(ans, append([]string{}, path...))
            return
        }

        for j, isColHave := range col{
            if !isColHave {
              // 当前列没有皇后
              // 斜线上是否有元素
              if isHave, ok := have1[i + j]; ok && isHave{
                  continue
              }
              if isHave, ok := have2[i - j]; ok && isHave{
                  continue
              }

              temp := append([]byte{}, modelByte...)
              temp[j] = 'Q'
              path[i] = string(append([]byte{}, temp...))

              col[j], have1[i + j], have2[i - j] = true, true, true
              dfs(i + 1)
              col[j], have1[i + j], have2[i - j] = false, false, false
            }
        }
    }
    dfs(0)
    return ans
}

优化后：

将判断斜线的哈希表改为布尔数组，path 的添加使用 strings.Repeat 方法

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 solveNQueens(n int) [][]string {
    var col = make([]bool, n) // 记录哪一列已经有皇后了
    var have1 = make([]bool, 2 * n) // 右斜线上是否有元素
    var have2 = make([]bool, 2 * n) // 左斜线上是否有元素

    var path = make([]string, n)
    var ans [][]string
    var dfs func(int)

    dfs = func(i int){
        if i == n{
            ans = append(ans, append([]string{}, path...))
            return
        }

        for j, isColHave := range col{
            ij := i - j + n - 1
            if !isColHave && !have1[i + j] && !have2[ij]{
              // 当前列没有皇后
              // 斜线上无元素

              path[i] = strings.Repeat(".", j) + "Q" + strings.Repeat(".", n - j - 1)
              col[j], have1[i + j], have2[ij] = true, true, true
              dfs(i + 1)
              col[j], have1[i + j], have2[ij] = false, false, false
            }
        }
    }
    dfs(0)
    return ans
}

LeetCode 52

思路

改一下 51 的返回值即可

代码实现

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 totalNQueens(n int) int {
    var col = make([]bool, n) // 记录哪一列已经有皇后了
    var have1 = make([]bool, 2 * n) // 右斜线上是否有元素
    var have2 = make([]bool, 2 * n) // 左斜线上是否有元素

    var path = make([]string, n)
    var ans int
    var dfs func(int)

    dfs = func(i int){
        if i == n{
            ans++
            return
        }

        for j, isColHave := range col{
            ij := i - j + n - 1
            if !isColHave && !have1[i + j] && !have2[ij]{
              // 当前列没有皇后
              // 斜线上无元素

              path[i] = strings.Repeat(".", j) + "Q" + strings.Repeat(".", n - j - 1)
              col[j], have1[i + j], have2[ij] = true, true, true
              dfs(i + 1)
              col[j], have1[i + j], have2[ij] = false, false, false
            }
        }
    }
    dfs(0)
    return ans
}