递归的三种形式
Published by powerfulyang on Jul 3, 2022
Memorization
将计算结果保存,避免重复计算。
Divide and Conquer
分治,将大问题分解成小问题,各个击破,然后将小问题组合起来。
- Divide
- Conquer
- Combine
Backtracking
回溯法用来解决 N 个 for 循环的问题
不断试错,知错就改。类似于暴力搜索, 但是会剪枝优化。
一般要求返回所有满足条件的解答。
例如 第77题
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。 循环的最大次数如何确定:
- startIndex 随着循环推移。
- 已经选择的元素个数: path.size();
- 还需要的元素个数为: k - path.size();
- 在集合n中至多要从该起始位置至 n - (k - path.size()) + 1 遍历,后面 (k - path.size - 1) 个元素是不需要遍历的。
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};
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};