跟着卡哥学算法Day 22：回溯算法理论 & 题目一

回溯法的效率#

回溯法暴力穷举时，可以通过剪枝来优化，即剪掉不需要处理的路径，从而减少不必要的搜索。

回溯法核心理解#

回溯法可以抽象为一个 n 叉树结构，树的宽度表示处理的集合的大小，树的高度表示递归的深度。

1. 解空间树模型

   • 将问题转化为树形结构的决策过程，每个节点代表一个决策步骤
   • 叶子节点对应问题的候选解，路径代表决策序列

2. 三要素

   • 路径：记录做出的选择
   • 选择列表：当前可做的选择，通常而言，用数组存储可以选择的操作
   • 结束条件：到达决策树底层，就是递归的结束点，也就是搜索的结束点

回溯法模板#

1
result = []
2

3
function backtrack(路径, 选择列表) {
4
  if ('满足结束条件') {
5
    // 记录结果
6
    result.push(路径)
7
    return
8
  } else {
9
    for (let i in 选择列表) {
10
      // 对一个选择列表做相应的选择
11

12
      做选择
13
      路径.push(选择)
14

15
      backtrack(新路径, 新选择列表)
16

17
      // 既然是回溯算法,那么在一次分岔路做完选择后
18
      // 需要回退我们之前做的操作
19
      // 保持路径状态一致性，确保不同分支间不互相干扰
20

21
      撤销选择
22
      路径.pop()
23
    }
24
  }
25
}

关键优化技巧#

1. 剪枝策略

   • 可行性剪枝：提前终止不可能产生解的分支

     1
     if 当前选择导致不可行: continue

   • 最优性剪枝：放弃非最优路径

     1
     if 当前路径已劣于已知最优解: continue

2. 记忆化搜索

   • 使用哈希表记录已访问状态，避免重复计算
   • 适用于存在重叠子问题的情况

3. 决策顺序优化

   • 优先选择约束强的决策，减少搜索空间
   • 例如数独求解时优先填充候选数少的格子

题目描述#

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

解题思路#

暴力法：两层 for 循环

1
for (let i = 0; i < n; i++) {
2
  for (let j = i + 1; j < n; j++) {
3
    result.push([i + 1, j + 1])
4
  }
5
}

但如果有 k>2 时，就需要多层 for 循环，暴力解法多层 for 循环嵌套很难写出来。

此时就需要使用回溯法来解决，用递归来解决多层嵌套循环的问题

回溯法解题步骤#

画图，将需要解决的问题抽象为 n 叉树

可以看出：n 相当于树的宽度，k 相当于树的高度

一维数组 path 来存放符合条件的结果，二维数组 result 来存放结果集

回溯三部曲：

1. 回溯函数返回值以及参数

   • 参数 1：n

   • 参数 2：k

   • 参数 3：startIndex，用于记录当前递归的起始位置

     1
     void backtracking(int n, int k, int startIndex)

2. 回溯函数终止条件

   到达叶子节点时结果递归函数，那么何时到底叶子节点呢？

   收集结果的数组大小等于 k 时，说明已经找到了子集大小为 k 的组合，结果中保存的就是根节点到叶子结点的路径。

   1
   if (path.length == k) {
   2
     result.push(path)
   3
     return
   4
   }

3. 单层搜索的过程

   for 循环可以理解是横向遍历每个元素，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了

   1
   for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
   2
       path.push(i); // 处理节点
   3
       backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
   4
       path.pop(); // 回溯，撤销处理的节点
   5
   }

代码#

1
function combine(n, k) {
2
  let result = []
3
  let path = []
4

5
  const backtracking = (n, k, startIndex) => {
6
    if (path.length == k) {
7
      result.push([...path])
8
      return
9
    }
10

11
    for (let i = startIndex; i <= n; i++) {
12
      path.push(i)
13
      backtracking(n, k, i + 1)
14
      path.pop()
15
    }
16
  }
17
  backtracking(n, k, 1)
18
  return result
19
}

1
function combine(n, k) {
2
  let result = []
3
  let path = []
4

5
  const backtracking = (n, k, startIndex) {
6
    if (path.length === k) {
7
      result.push([...path])
8
      return
9
    }
10
    const remaining = k - path.length
11
    for (let i = startIndex; i <= n - remaining + 1; i++) {
12
      path.push(i)
13
      backtracking(n, k, i + 1)
14
      path.pop()
15
    }
16
  }
17
  backtracking(n, k, 1)
18
  return result
19
}

题目描述#

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

解题思路#

本题：k 相当于树的深度，9 就是树的宽度，即在组合[1,2,3,4,5,6,7,8,9]中求 k 个数和为 n 的组合。

此时依然使用一维数组 path 来存放符合条件的结果，二维数组 result 来存放结果集

回溯三部曲：

1. 回溯函数返回值以及参数

   • 参数 1：n

   • 参数 2：k

   • 参数 3：startIndex，用于记录当前递归的起始位置

   • 参数 4：sum，存储当前路径的和，path 内元素的总和

     1
     void backtracking(n, k, startIndex, sum)

2. 回溯函数终止条件

   到达叶子节点时结果递归函数，那么何时到底叶子节点呢？

   收集结果的数组大小等于 k 时，并且 sum 等于 n，使用 result 收集。

   1
   if (path.length == k) {
   2
     if (sum === n) result.push(path)
   3
     return
   4
   }

3. 单层搜索的过程

   for 循环可以理解是横向遍历每个元素，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了

   1
   for (int i = startIndex; i <= 9; i++) { // 控制树的横向遍历
   2
       path.push(i); // 处理节点
   3
       sum += i
   4
       backtracking(n, k, i + 1, sum); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
   5
       path.pop(); // 回溯，撤销处理的节点
   6
       sum -= i
   7
   }

代码#

1
var combinationSum3 = function (k, n) {
2
  let result = []
3
  let path = []
4

5
  const backtracking = (startIndex, sum) => {
6
    if (path.length === k) {
7
      if (n === sum) result.push([...path])
8
      return
9
    }
10

11
    for (let i = startIndex; i <= 9; i++) {
12
      path.push(i)
13
      sum += i
14
      backtracking(i + 1, sum)
15

16
      sum -= i
17
      path.pop()
18
    }
19
  }
20
  backtracking(1, 0)
21

22
  return result
23
}

1
var combinationSum3 = function (k, n) {
2
  let result = []
3
  let path = []
4

5
  const backtracking = (startIndex, sum) => {
6
    // 剪枝：和超过目标值
7
    if (sum > n) return
8
    if (path.length === k) {
9
      if (n === sum) result.push([...path])
10
      return
11
    }
12
    // 计算剩余需要的数字数量
13
    const need = k - path.length
14
    // 剪枝：i的上界为 9 - need + 1
15
    for (let i = startIndex; i <= 9 - need + 1; i++) {
16
      path.push(i)
17
      sum += i
18
      backtracking(i + 1, sum)
19

20
      sum -= i
21
      path.pop()
22
    }
23
  }
24
  backtracking(1, 0)
25

26
  return result
27
}

题目描述#

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例:

• 输入：“23”
• 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序

解题思路#

本题：输入数字的个数相当于树的深度，每个按键对应的字母就是树的宽度

此时依然使用字符串 s 来存放符合条件的结果，数组 result 来存放结果集

回溯三部曲：

1. 回溯函数返回值以及参数

   • 参数 1：index 当前处理的数字位置

2. 回溯函数终止条件

   当 index 等于数字个数，那么使用 result 收集结果

   1
   if (index === digits.length) {
   2
     result.push(currentStr)
   3
     return
   4
   }

3. 单层搜索的过程

   for 循环可以理解是遍历当前数字对应的所有字母，backtracking（递归）就是纵向遍历，处理下一个数字

   1
   for (let char in letters) {
   2
   }

代码#

1
function letterCombinations(digits) {
2
  if (!digits?.length) return []
3

4
  const result = []
5
  const path = []
6
  const map = {
7
    2: 'abc',
8
    3: 'def',
9
    4: 'ghi',
10
    5: 'jkl',
11
    6: 'mno',
12
    7: 'pqrs',
13
    8: 'tuv',
14
    9: 'wxyz',
15
  }
16

17
  const backtracking = (index) => {
18
    if (path.length === digits.length) {
19
      result.push(path.join(''))
20
      return
21
    }
22

23
    const letters = map[digits[index]]
24
    for (let char of letters) {
25
      path.push(char)
26
      backtracking(index + 1)
27
      path.pop()
28
    }
29
  }
30
  backtracking(0)
31
  return result
32
}