跟着灵茶山艾府大佬学习算法思路的day9，目标是在一个月内掌握hot100
b站链接如下：
递归大概有两大流派：
- 分治型递归：拆独立子问题，合并结果（二叉树高度、归并排序、快排）
- 回溯型递归：在部分解上逐步延伸，穷举所有方案（子集、排列、组合）
回溯类问题可以分为子集型回溯、组合型回溯和排列型回溯。0-1背包问题也算是一种子集型回溯。
电话号码的字母组合 题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
1
2
输入：digits = "2"
输出：["a","b","c"]
思路：
单纯的循环嵌套表达能力是有局限的，但通过递归可以达到多重循环的效果。增量构造答案的过程就是回溯的特点，这个过程通常就用递归实现。只要把边界条件和非边界条件写对，那递归就一定是对的，其他部分可以完全交给数学归纳法，不用想太多。
灵神的套路：回溯三问
递归参数中的i不是第i个，而是大于等于i的这部分问题仍然尚待枚举。
代码：
var letterCombinations = function(digits) {
if (!digits.length) return [];
const map = {
2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl',
6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'
};
const ans = [];
const path = []; // 当前路径
function backtrack(index) {
// 终止条件：所有数字都处理完了
if (index === digits.length) {
ans.push(path.join('')); // 把路径数组转成字符串，然后存进结果数组
return;
}
// 遍历当前数字对应的所有字母
for (const ch of map[digits[index]]) { // 字符串的可迭代性
path.push(ch); // 做选择
backtrack(index + 1); // 递归处理下一个数字
path.pop(); // 撤销选择（回溯）
}
}
backtrack(0);
return ans;
};
总结：
回溯类的题目基本就是dfs加上剪枝，也总是涉及push和pop的操作，因为需要记录经过的所有路径，如果只是前序遍历那样只需要知道当前到达的节点，是不需要对路径push和pop的，这两个操作已经被递归的调用隐式地完成了。
子集 题目描述：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
1
2
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
思路：
这道题最重要的就是将原问题往树的构造上思考。
第一种方法是从构造答案的思路来思考，可以称之为对于某个元素的选或不选。这样构造的树是二叉树，只有叶子结点构成答案。
第二种方法是直接从最终的所有答案的角度出发，枚举第几个数应该选什么数，这样构造的树就是一个n叉树，每个节点都是答案。为避免子集重复，可以规定枚举的数的索引必须递增。
代码：
选或不选二叉树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var subsets = function(nums) {
const n = nums.length;
const ans = []
const path = []
// 选或不选：讨论 nums[i] 是否加入 path
function dfs(i) {
if (i === n) { // 子集构造完毕
ans.push(path.slice()); // 复制 path
return;
}
// 不选 nums[i]，直接 + 1
dfs(i + 1); // 考虑下一个数 nums[i+1] 选或不选
// 选 nums[i]
path.push(nums[i]);
dfs(i + 1); // 考虑下一个数 nums[i+1] 选或不选
path.pop(); // 恢复现场，撤销 path.push(nums[i])
}
dfs(0);
return ans;
};
枚举n叉树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var subsets = function(nums) {
const n = nums.length;
const ans = []
const path = []
// 枚举选哪个：在下标 i 到 n-1 中选一个数，加到 path 末尾
function dfs(i) {
ans.push(path.slice()); // 把当前子集加入答案
for (let j = i; j < n; j++) { // 枚举能够被选择的数字
path.push(nums[j]); // 选入当前数字
dfs(j + 1); // 选 nums[j] 意味着 i 到 j-1 都跳过不选，下一个数从 j+1 开始选
path.pop(); // 恢复现场，弹出当前数字
}
}
dfs(0);
return ans;
};
总结：
对于后续 DP 学习来说，用的最多的是选或不选，枚举选哪个相对少一些。
分割回文串 题目描述：
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
1
2
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
思路：
枚举每个字符之间的逗号，对于每个逗号的是否选择插入，就构成了子集问题。
代码：
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
var isPalindrome = function(s, left, right) {
while (left < right) {
if (s.charAt(left++) !== s.charAt(right--)) {
return false;
}
}
return true;
}
var partition = function(s) {
const n = s.length;
const ans = [];
const path = [];
// 现在 s 未被分割的部分为 [i, n-1]
// 枚举下一刀切在哪
function dfs(i) {
if (i === n) { // 目前的path已经记录了一组回文切割，对应一个子集，分割完毕
ans.push(path.slice()); // 复制 path
return;
}
for (let j = i; j < n; j++) { // 枚举子串的结束位置
if (isPalindrome(s, i, j)) { // 判断 [i, j] 是不是回文串
path.push(s.substring(i, j + 1)); // 分割！
// 现在 s 未被分割的部分为 [j+1, n-1]
dfs(j + 1);
path.pop(); // 恢复现场
}
}
}
dfs(0);
return ans;
};
总结：
子集题里每个选择都合法，这题多了一个条件：只有 s[i…j] 是回文才能在这里切，也就是添加逗号。所以 for 循环里加了 if (isPalindrome(s, i, j)) 过滤。换句话说，每一个逗号插入方式实际上对应了一个子集问题的一个子集，但是这题要筛去一些子集。
做这题不必要纠结回文串到底要怎么切怎么构成，我们只需要关注一点，逗号到底能不能加，然后通过isPalindrome剪枝。