highlight: an-old-hope
theme: channing-cyan
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。——摘自《百度百科》
首先先说明一下对递归 (Recursive)与回溯 (Backtrack)的理解。
程序调用自身的编程技巧称为递归。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。 ——摘自《百度百科》
通常来说,为了描述问题的某一状态,必须用到该状态的上一个状态;而如果要描述上一个状态,又必须用到上一个状态的上一个状态…… 这样用自己来定义自己的方法就是递归。
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。 ——摘自《百度百科》
在这种思想下,我们需要清晰的找出三个要素:选择 (Options),限制 (Restraints),结束条件 (Termination)。
递归是一种算法结构。递归会出现在子程序中,形式上表现为直接或间接的自己调用自己。典型的例子是阶乘,计算规律为:n!=n×(n?1)!n!=n \times (n-1)!,基本如下所示:
let fac = (n)=> {
if(n == 1){
return n;
}else{
return (n*fac(n - 1));
}
}
回溯是一种算法思想,它是用递归实现的。回溯的过程类似于穷举法,但回溯有“剪枝”功能,即自我判断过程。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
提示:
1 <= n <= 8
var generateParenthesis = function (n) {
const res = [];
const backTracing = (lRemain, rRemain, str) => { // 左右括号所剩的数量,str是当前构建的字符串
if (str.length == 2 * n) { // 字符串构建完成
res.push(str); // 加入解集
return; // 结束当前递归分支
}
if (lRemain > 0) { // 只要左括号有剩,就可以选它,然后继续做选择(递归)
backTracing(lRemain - 1, rRemain, str + "(");
}
if (lRemain < rRemain) { // 右括号比左括号剩的多,才能选右括号
backTracing(lRemain, rRemain - 1, str + ")"); // 然后继续做选择(递归)
}
};
backTracing(n, n, ""); // 递归的入口,剩余数量都是n,初始字符串是空串
return res;
};
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1]
输出:[[1]]
提示:
1 <= nums.length <= 6
-10 <= numsi <= 10
nums 中的所有整数 互不相同
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
if (!nums.length) return
let res = []
let backTrack = path => {
//长度满足条件,加入结果
if (path.length === nums.length) {
res.push(path)
return
}
nums.forEach(item => {
if (path.includes(item)) return //不包含重复的数字
backTrack([...path, item]) //加入路径,继续递归选择
});
}
backTrack([])
return res
};
图片上传失败...(image-40cdd5-1639281547994)
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。***
皇后的走法是:可以横直斜走,格数不限。因此要求皇后彼此之间不能相互攻击,等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。
示例 1:
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:1
提示:
1 <= n <= 9
var totalNQueens = function (n) {
let count = 0; //皇后可放置的总数
let isValid = (row, col, board, n) => {
//所在行不用判断,每次都会下移一行
//判断同一列的数据是否包含
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') {
return false
}
}
//判断45度对角线是否包含
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') {
return false
}
}
//判断135度对角线是否包含
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) {
if (board[i][j] === 'Q') {
return false
}
}
return true
}
let backTracing = (row, board) => {
//走到最后一行,统计次数
if (row === n) {
count++;
return
}
for (let x = 0; x < n; x++) {
//判断该位置是否可以放置 皇后
if (isValid(row, x, board, n)) {
board[row][x] = 'Q'; //放置皇后
backTracing(row + 1, board); //递归
board[row][x] = '.'; //回溯,撤销处理结果
}
}
}
backTracing(0, board)
let board = [...Array(n)].map(v => v = ([...Array(n)]).fill('.')) //棋盘
return count
};
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= numsi <= 10
nums 中的所有元素 互不相同
const subsets = (nums) => {
const res = [];
const backTracing = (index, list) => {
res.push(list.slice()); // 调用子递归前,加入解集
for (let i = index; i < nums.length; i++) { // 枚举出所有可选的数
list.push(nums[i]); // 选这个数
backTracing(i + 1, list); // 基于选这个数,继续递归
list.pop(); // 撤销选这个数
}
};
backTracing(0, []);
return res;
};
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2:
输入:n = 1, k = 1
输出:[[1]]
提示:
1 <= n <= 20
1 <= k <= n
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
let result = [];
let backTracing = (start, path) => {
// 如果已经选满了的话,加入结果集中
if (path.length == k) {
result.push(path.slice());
return;
}
// 从开始的数字到末尾的数字
for (let i = start; i <= n; i++) {
// 加入选择列表中
path.push(i);
// 继续深度搜索
backTracing(i + 1, path);
// 撤销选择
path.pop(i);
}
};
backTracing(1, []);
return result;
};
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同,则两种组合是唯一的。
对于给定的输入,保证和为 target 的唯一组合数少于 150 个。
示例 1:
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1
输出: []
示例 4:
输入: candidates = [1], target = 1
输出: [[1]]
示例 5:
输入: candidates = [1], target = 2
输出: [[1,1]]
提示:
1 <= candidates.length <= 30
1 <= candidatesi <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
var combinationSum = function (candidates, target) {
const result = [], visited = [];
backTracing(0, 0);
return result;
function backTracing(sum, cur) {
if (target === sum) result.push(visited.slice());
if (target <= sum) return;
for (let i = cur; i < candidates.length; i++) {
visited.push(candidates[i]); //加入到选项里面
backTracing(sum + candidates[i], i);//选择这个选项,继续递归
visited.pop(); //插销这个选择
}
}
};
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
同组合1
var combinationSum3 = function (k, n) {
let ans = [];
let backTracing = (start, path) => {
if (path.length === k && path.reduce((acc, prev) => acc += prev) === n) {
ans.push(path.slice())
return
}
for (let i = start; i <= 9; i++) {
path.push(i)
backTracing(i + 1, path)
path.pop(i)
}
}
backTracing(1, [])
return ans
};
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = ""
输出:[]
示例 3:
输入:digits = "2"
输出:["a","b","c"]
提示:
0 <= digits.length <= 4
digitsi 是范围 '2', '9' 的一个数字。
var letterCombinations = function (digits) {
if(!digits.length) return []
const dic = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz',
}, ans = [];
let backTracing = (cur, index) => {
if (index > digits.length - 1) { //选项满足长度,加入结果
ans.push(cur)
return
}
let curDic = dic[digits[index]] //找到当前按钮对应的字母字符串
for (let prop of curDic) {
backTracing(cur + prop,index+1) //拼接按钮对应的字符串组合
}
}
backTracing('', 0)
return ans
};
示例1:
输入:n = 3
输出:4
说明: 有四种走法
示例2:
输入:n = 5
输出:13
提示:
n范围在1, 1000000之间
var waysToStep = function (n) {
let ans = [], map = [1, 2, 3]
let backTracing = (path, sum) => {
if (sum >= n) {
if (sum == n) {
ans++;
}
return
}
for (let i = 0; i < 3; i++) {
path.push(map[i]);
backTracing(path, sum + map[i])
path.pop(i)
}
}
backTracing([], 0)
return ans
};
/**
* @param {number} n
* @return {number}
*/
var waysToStep = function (n) {
let dp =[],mod = 1000000007;
dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=4;
for (let i = 4; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod
}
return dp[n]
};
candidates 中的每个数字在每个组合中只能使用一次。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidatesi <= 50
1 <= target <= 30
思路同组合1
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
candidates.sort((a,b)=>a-b)
let ans = [];
let backTracing = (start, path, sum) => {
if (sum >= target) {
if (sum === target) {
ans.push(path.slice())
}
return
}
for (let i = start; i < candidates.length; i++) {
if (i - 1 >= start && candidates[i - 1] == candidates[i]) {
continue;
}
path.push(candidates[i])
backTracing(i + 1, path, sum + candidates[i])
path.pop()
}
}
backTracing(0, [], 0)
return ans
};
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示:
1 <= nums.length <= 8
-10 <= numsi <= 10
同上全排列
var permuteUnique = function (nums) {
let ans = [];
let used = Array(nums.length).fill(false)
let backTracing = (start, path) => {
if (start === nums.length) {
ans.push(path.slice())
return
}
for (let i = 0; i < nums.length; ++i) {
if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
continue;
}
path.push(nums[i])
used[i] = true
backTracing(start + 1, path)
used[i] = false
path.pop()
}
}
nums.sort((a, b) => a - b)
backTracing(0, [])
return ans
};
# 三、总结
### 主要运用了回溯算法;而解决一个回溯问题,实际上就是一个决策树的遍历过程。
## 3.1 模板
```js
let backtracking=(路径,选择列表) =>{
if (满足结束条件)) {
存放路径;
return;
}
for (选择:路径,选择列表) {
做出选择;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
即:
继续加油!!!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。