递归的三种形式

Published by powerfulyang on Jul 3, 2022

Memorization

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

Divide and Conquer

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

  1. Divide
  2. Conquer
  3. Combine

Backtracking

回溯法用来解决 N 个 for 循环的问题
不断试错，知错就改。类似于暴力搜索, 但是会剪枝优化。 一般要求返回所有满足条件的解答。

例如 第77题

typescript
1function backtrack(n: number, k: number, startIndex: number, path: number[], result: number[][]) {
2  if (path.length === k) {
3    result.push([...path]);
4    return;
5  }
6
7  for (let i = startIndex; i <= n; i++) {
8    path.push(i);
9    backtrack(n, k, i + 1, path, result);
10    path.pop();
11  }
12}
13
14/**
15 * #77, https://leetcode.cn/problems/combinations/
16 */
17export const Combine = (n: number, k: number): number[][] => {
18  const result: number[][] = [];
19  const path: number[] = [];
20  backtrack(n, k, 1, path, result);
21  return result;
22};
  • 递归函数的返回值以及参数
    一般定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
    还需要一个参数 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
1function backtrack(n: number, k: number, startIndex: number, path: number[], result: number[][]) {
2  if (path.length === k) {
3    result.push([...path]);
4    return;
5  }
6
7  for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
8    path.push(i);
9    backtrack(n, k, i + 1, path, result);
10    path.pop();
11  }
12}
13
14/**
15 * #77, https://leetcode.cn/problems/combinations/
16 */
17export const Combine = (n: number, k: number): number[][] => {
18  const result: number[][] = [];
19  const path: number[] = [];
20  backtrack(n, k, 1, path, result);
21  return result;
22};

电话号码的字母组合

typescript
1function letterCombinations(digits: string): string[] {
2    const len = digits.length;
3    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
4    if (!len) {
5        return [];
6    }
7    if (len === 1) {
8        return map[digits].split("");
9    }
10    const ans = [];
11    const path = [];
12
13    function backtracking(n: string, k: number, startIndex: number) {
14        if (path.length === k) {
15            ans.push(path.join(''));
16            return;
17        }
18        for (const v of map[n[startIndex]]) {
19            path.push(v);
20            backtracking(n, k, startIndex + 1);
21            path.pop();
22        }
23    }
24
25    backtracking(digits, len, 0);
26    return ans;
27};