递归的三种形式

Memorization

将计算结果保存,避免重复计算。

Divide and Conquer

分治,将大问题分解成小问题,各个击破,然后将小问题组合起来。

  1. Divide
  2. Conquer
  3. Combine

Backtracking

不断试错,知错就改。类似于暴力搜索, 但是会剪枝优化。 一般要求返回所有满足条件的解答。

例如 第77题

typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function backtrack(n: number, k: number, startIndex: number, path: number[], result: number[][]) {
  if (path.length === k) {
    result.push([...path]);
    return;
  }

  for (let i = startIndex; i <= n; i++) {
    path.push(i);
    backtrack(n, k, i + 1, path, result);
    path.pop();
  }
}

/**
 * #77, https://leetcode.cn/problems/combinations/
 */
export const Combine = (n: number, k: number): number[][] => {
  const result: number[][] = [];
  const path: number[] = [];
  backtrack(n, k, 1, path, result);
  return result;
};
  • 递归函数的返回值以及参数
    一般定义两个全局变量,一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。
    还需要一个参数 startIndex, 每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex。
  • 回溯函数终止条件
  • 剪枝优化

上面题目的回溯函数终止条件为: path.length === k。 循环的最大次数如何确定:

  1. startIndex 随着循环推移。
  2. 已经选择的元素个数: path.size();
  3. 还需要的元素个数为: k - path.size();
  4. 在集合n中至多要从该起始位置至 n - (k - path.size()) + 1 遍历,后面 (k - path.size - 1) 个元素是不需要遍历的
typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function backtrack(n: number, k: number, startIndex: number, path: number[], result: number[][]) {
  if (path.length === k) {
    result.push([...path]);
    return;
  }

  for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
    path.push(i);
    backtrack(n, k, i + 1, path, result);
    path.pop();
  }
}

/**
 * #77, https://leetcode.cn/problems/combinations/
 */
export const Combine = (n: number, k: number): number[][] => {
  const result: number[][] = [];
  const path: number[] = [];
  backtrack(n, k, 1, path, result);
  return result;
};