开始学习了，希望我可以尽快成功上岸！
一、回溯理论基础
- 什么是回溯法？
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
- 回溯法的效率
回溯法的本质是穷举，穷举所有可能，然后找出我们想要的答案。如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
组合无序，排列有序。
-
回溯法模板
回溯三部曲，可以按照如下步骤：
-
回溯函数模板返回值以及参数
-
回溯函数终止条件
-
回溯搜索的遍历过程
回溯函数遍历过程伪代码如下：
-
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
-
处理节点;
-
backtracking(路径，选择列表); // 递归
-
回溯，撤销处理结果
-
}
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：
-
void backtracking(参数) {
-
if (终止条件) {
-
存放结果;
-
return;
-
}
-
-
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
-
处理节点;
-
backtracking(路径，选择列表); // 递归
-
回溯，撤销处理结果
-
}
-
}
- 总结
回溯和递归是相辅相成的。
回溯法其实就是暴力查找，并不是什么高效的算法。
二、组合
题目链接：77. 组合
题目描述：
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。
来看一下Js代码，是按照卡尔的官方视频讲解写出来的，提交leetcode是可以通过的：
-
/**
-
* @param {number} n
-
* @param {number} k
-
* @return {number[][]}
-
*/
-
var combine = function (n, k) {
-
// 回溯法
-
let result = [],
-
path = [];
-
let backtracking = (_n, _k, startIndex) => {
-
// 终止条件
-
if (path.length === _k) {
-
result.push(path.slice());
-
return;
-
}
-
// 循环本层集合元素
-
for (let i = startIndex; i <= _n; i++) {
-
path.push(i);
-
// 递归
-
backtracking(_n, _k, i + 1);
-
// 回溯操作
-
path.pop();
-
}
-
};
-
backtracking(n, k, 1);
-
return result;
-
};
剪枝操作：
-
/**
-
* @param {number} n
-
* @param {number} k
-
* @return {number[][]}
-
*/
-
var combine = function(n, k) {
-
const res = [], path = [];
-
backtracking(n, k, 1);
-
return res;
-
function backtracking (n, k, i){
-
const len = path.length;
-
if(len === k) {
-
res.push(Array.from(path));
-
return;
-
}
-
for(let a = i; a <= n + len - k + 1; a++) {
-
path.push(a);
-
backtracking(n, k, a + 1);
-
path.pop();
-
}
-
}
-
};
三、电话号码的字母组合
题目链接：17. 电话号码的字母组合
题目描述：
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
看一下具体的JS代码吧
-
/**
-
* @param {string} digits
-
* @return {string[]}
-
*/
-
var letterCombinations = function(digits) {
-
const twoArr = [
-
"", // 0
-
"", // 1
-
"abc", // 2
-
"def", // 3
-
"ghi", // 4
-
"jkl", // 5
-
"mno", // 6
-
"pqrs", // 7
-
"tuv", // 8
-
"wxyz", // 9
-
]
-
let s = []
-
let result = [];
-
const backtraking = (digits, index) => {
-
if (index == digits?.length) {
-
const str = s.join('')
-
if (!str) {
-
return result;
-
}
-
result.push(str)
-
return;
-
};
-
const digit = Number(digits.charAt(index))
-
const stringLetter = twoArr[digit];
-
for (let i =0;i <stringLetter.length;i++) {
-
console.log(stringLetter.charAt(i))
-
s.push(stringLetter.charAt(i))
-
backtraking(digits, index + 1);
-
s.pop();
-
}
-
-
-
}
-
backtraking(digits, 0)
-
return result;
-
};
四、组合总和III
题目链接：216. 组合总和 III
题目描述：
找出所有相加之和为
n的k个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
来看一下按照卡尔的官方视频讲解写出来的JS代码吧：
-
/**
-
* @param {number} k
-
* @param {number} n
-
* @return {number[][]}
-
*/
-
var combinationSum3 = function(k, n) {
-
let path = [], result = [];
-
-
const backtracking = (targetSum, k, sum, startIndex) => {
-
// 剪枝操作
-
if (sum > targetSum) {
-
return;
-
}
-
// 终止条件
-
if (path?.length === k) {
-
if (targetSum == sum) {
-
result.push(path.slice());
-
}
-
return
-
}
-
// 剪枝操作,至多指向那个nMax就可以了，再向后就没有意义了。
-
const nMax = 9 - (k - path.length) + 1;
-
for(let i = startIndex; i<= nMax;i++) {
-
sum += i;
-
path.push(i);
-
backtracking(targetSum, k, sum, i + 1);
-
sum -= i;
-
path.pop();
-
}
-
};
-
-
backtracking(n, k, 0, 1)
-
-
return result;
-
};