回溯算法详解
站长
· 阅读数 27
定义
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
用回溯算法解决问题的一般步骤：
- 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
- 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
- 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
回溯是经过修改的深度优先查找方法，过程包括：对一个状态空间树进行深度优先查找，检查每个节点是否满足条件。如果不满足就回溯到该节点的父节点。算法框架(伪代码)如下：
result = []
backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
核心就是for循环里面的递归, 在递归调用之前做选择, 递归调用之后撤销选择。
回溯解法题
下面是一些典型的回溯题，也是我自己刷过的题。
全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源: leetcode-cn.com/problems/pe…
var permute = function(nums) {
let len = nums.length;
let res = [];
function backTrace(path) {
if(path.length === len) return res.push(path.slice());
for (let i = 0; i < len; i++) {
if(path.indexOf(nums[i]) === -1) {
path.push(nums[i]);
backTrace(path);
path.pop();
}
}
}
backTrace([]);
return res;
};
全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
来源: leetcode-cn.com/problems/pe…
var permuteUnique = function(nums) {
let len = nums.length, res = [], idx = [];
nums.sort((a, b) => a - b);
function backTrace(path, idx) {
if(path.length === len) return res.push(path.slice());
for (let i = 0; i < len; i++) {
if((nums[i] === nums[i - 1] && idx.includes(i - 1)) || idx.includes(i)) continue;
path.push(nums[i]);
idx.push(i);
backTrace(path, idx);
path.pop();
idx.pop();
}
}
backTrace([], idx);
return res;
};
子集
给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。**说明：**解集不能包含重复的子集。
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
来源: leetcode-cn.com/problems/su…
var subsets = function(nums) {
let path = [], res = [];
let backTrace = (start, nums, path, res) => {
if(path.length > nums.length) return;
res.push(path.slice());
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
backTrace(i + 1, nums, path, res);
path.pop()
}
}
backTrace(0, nums, path, res);
return res;
};
子集 II
给定一个可能包含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。**说明：**解集不能包含重复的子集。
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
来源: leetcode-cn.com/problems/su…
var subsetsWithDup = function(nums) {
let path = [], res = [];
nums.sort((a, b) => a - b);
let backTrace = (start, nums, path, res) => {
if(path.length > nums.length) return;
res.push(path.slice());
for (let i = start; i < nums.length; i++) {
if(start < i && nums[i - 1] === nums[i]) continue;
path.push(nums[i]);
backTrace(i + 1, nums, path, res);
path.pop();
}
}
backTrace(0, nums, path, res);
return res;
};
组合
给定两个整数n和k，返回 1 ...n中所有可能的k个数的组合。
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
来源: leetcode-cn.com/problems/co…
var combine = function(n, k) {
let res = [], path = [];
if(k === 0) return [[]];
function backTrace(start, n, k, path, res) {
if(path.length === k) return res.push(path.slice());
for (let i = start; i <= n; i++) {
path.push(i);
backTrace(i + 1, n, k, path, res);
path.pop();
}
}
backTrace(1, n, k, path, res);
return res;
};
组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
来源: leetcode-cn.com/problems/co…
var combinationSum = function(candidates, target) {
let res = [], path = [], len = candidates.length;
candidates.sort((a, b) => a - b);
function backTrace(path, target, start) {
if(target === 0) return res.push(path.slice());
for (let i = start; i < len; i++) {
if(target < candidates[i]) break;
path.push(candidates[i]);
backTrace(path, target - candidates[i], i);
path.pop(candidates[i]);
}
}
backTrace(path, target, 0);
return res;
};
组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
来源: leetcode-cn.com/problems/co…
var combinationSum2 = function(candidates, target) {
let res = [], path = [], len = candidates.length;
candidates.sort((a, b) => a - b);
function backTrace(path, target, start) {
if(target === 0) return res.push(path.slice());
for (let i = start; i < len; i++) {
if(candidates[i] > target) continue;
if(i > start && candidates[i - 1] === candidates[i]) continue;
path.push(candidates[i]);
backTrace(path, target - candidates[i], i + 1);
path.pop();
}
}
backTrace(path, target, 0);
return res;
};
组合总和 III
找出所有相加之和为n的k个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
来源: leetcode-cn.com/problems/co…
var combinationSum3 = function(k, n) {
let path = [], res = [];
function backTrace(start, k, n, res, path) {
if(path.length === k && n === 0) return res.push(path.slice());
for (let i = start; i < 10; i++) {
path.push(i);
backTrace(i + 1, k, n - i, res, path);
path.pop();
}
}
backTrace(1, k, n, res, path);
return res;
};
字符串的排列
输入一个字符串(有重复字符串的排列组合)，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
来源: leetcode-cn.com/problems/zi…
var permutation = function(s) {
let ans = [];
function dfs(cur, str) {
if(str === '') return ans.push(cur);
for (let i = 0, len = str.length; i < len; i++) {
if(i > 0 && str[i - 1] === str[i]) continue;
cur += str[i];
dfs(cur, str.slice(0, i).concat(str.slice(i + 1)))
cur = cur.slice(0, cur.length - 1)
}
}
dfs('', s.split('').sort().join(''));
return ans;
};
无重复字符串的排列组合
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
输入：S = "qwe"
输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
来源: leetcode-cn.com/problems/pe…
var permutation = function(S) {
let cur = '', ans = [];
let backtrace = (cur, str) => {
if(str === '') {
ans.push(cur);
}
for (let i = 0, len = str.length; i<len; i++) {
cur += str[i];
backtrace(cur, str.slice(0, i).concat(str.slice(i+1)));
cur = cur.slice(0, cur.length - 1);
}
}
backtrace(cur, S);
return ans;
};
顺次数
我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。 请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。
输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]
来源: leetcode-cn.com/problems/se…
var sequentialDigits = function(low, high) {
let ans = [];
for (i = 1; i <= 9; i++) {
backtrack(low, high, i, i);
}
ans.sort((a, b) => a-b)
return ans;
function backtrack (low, high, curNum, curTail) {
if(curNum >= low && curNum <= high) {
ans.push(curNum);
}
if(curNum > high) {
return;
}
if(curTail + 1 <= 9) {
backtrack(low, high, curNum*10 + curTail + 1, curTail + 1)
}
}
};
复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
来源: leetcode-cn.com/problems/re…
var restoreIpAddresses = function(s, res = [], arr = [], start = 0) {
if(s.length > 12 || s.length < 4) return res;
if(arr.length === 4 && start === s.length) res.push(arr.join('.'));
for (let i = start; i < s.length; i++) {
let str = s.substring(start, i + 1), strNum = str - 0;
if(strNum > 255 || str != strNum + '') break;
arr.push(str);
restoreIpAddresses(s, res, arr, i+1);
arr.pop();
}
return res;
};
分割回文串
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。
输入: "aab"
输出:
[ ["aa","b"],
["a","a","b"]
]
来源: leetcode-cn.com/problems/pa…
var partition = function(s) {
let ans = [], path = [];
let backTrace = (start, path) => {
if(start === s.length) return ans.push(path.slice());
for (let i = start; i < s.length; i++) {
if(!isPalindrome(start, i)) continue;
path.push(s.slice(start, i + 1));
backTrace(i + 1, path);
path.pop();
}
}
function isPalindrome(start, end) {
let l = start, h = end;
while(l < h) {
if(s[l++] !== s[h--]) return false;
}
return true;
}
backTrace(0, path);
return ans;
};
字母大小写全排列
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
输入：S = "3z4"
输出：["3z4", "3Z4"]
输入：S = "12345"
输出：["12345"]
来源: leetcode-cn.com/problems/le…
var letterCasePermutation = function(S) {
const res = [];
const backTrace = (start, str) => {
res.push(str);
for (let i = start; i < str.length; i++) {
if(str[i] >= 'a' && str[i] <= 'z') {
backTrace(i+1, str.slice(0, i) + str[i].toUpperCase() + str.slice(i+1));
} else if(str[i] >= 'A' && str[i] <= 'Z') {
backTrace(i+1, str.slice(0, i) + str[i].toLowerCase() + str.slice(i+1));
}
}
}
backTrace(0, S);
return res;
};
括号生成
数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 3
输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
来源: leetcode-cn.com/problems/ge…
var generateParenthesis = function(n) {
if(!n) return [];
let res = [];
let dfs = (subs, left, right, n) => {
if(left === n && right === n) {
res.push(subs);
return;
}
if(left < right) {
return;
}
left < n && dfs(subs + '(', left + 1, right, n);
right < n && dfs(subs + ')', left, right + 1, n);
}
dfs('', 0, 0, n);
return res;
};
N 皇后
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
输入：4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],
["..Q.", // 解法 2 "Q...", "...Q", ".Q.."]
]
来源: leetcode-cn.com/problems/ei…
var solveNQueens = function(n) {
// 数组索引是行号，数组元素是列号
let queens = new Array(n);
let res = [];
// 标记着某一列是否有皇后
let cols = new Array(n);
// 标记着某一斜线上是否有皇后（左上角 -> 右下角）
let leftTop = new Array((n << 1) - 1);
// 标记着某一斜线上是否有皇后（右上角 -> 左下角）
let rightTop = new Array(leftTop.length);
place(0);
return res;
function place(row) {
if(row === cols.length) {
let arr = [];
for (let i in queens) {
arr.push('Q'.padStart(queens[i] + 1, '.').padEnd(n, '.'))
}
res.push(arr)
return res;
}
for (let col = 0; col < cols.length; col++) {
if(cols[col]) continue;
// 计算从左上角到右下角的索引值
let ltIndex = row - col + cols.length - 1;
if(leftTop[ltIndex]) continue;
// 计算右上角到左下角的索引值
let rtIndex = row + col;
if(rightTop[rtIndex]) continue;
queens[row] = col;
cols[col] = true;
leftTop[ltIndex] = true;
rightTop[rtIndex] = true;
place(row + 1);
cols[col] = false;
leftTop[ltIndex] = false;
rightTop[rtIndex] = false;
}
}
};
var solveNQueens = function(n) {
if(n < 1) return;
let res = [];
// 数组索引是行号，数组元素是列号
let cols = new Array(n);
place(0);
return res;
function place(row) {
if(row === n) {
show();
return;
}
for (let col = 0; col < n; col++) {
if(isValid(row, col)) {
cols[row] = col;
place(row + 1);
}
}
}
function isValid(row, col) {
for (let i = 0; i < row; i++) {
if(cols[i] === col) {
return false;
}
if(row - i === Math.abs(col - cols[i])) {
return false;
}
}
return true;
}
function show() {
let arr = [];
for (let row = 0; row < n; row++) {
for (let col = 0; col < n; col++) {
if(cols[row] === col) {
arr.push('Q'.padStart(cols[row] + 1, '.').padEnd(n, '.'))
}
}
}
res.push(arr);
}
};
N皇后 II
n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数n，返回n皇后不同的解决方案的数量。
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
来源: leetcode-cn.com/problems/n-…
var totalNQueens = function(n) {
let counts = 0;
let cols = new Array(n);
let leftTop = new Array((n << 1) - 1);
let rightTop = new Array(leftTop.length);
place(0);
return counts;
function place(row) {
if(row === cols.length) {
counts++;
return;
}
for (let col = 0; col < cols.length; col++) {
if(cols[col]) continue;
let ltIndex = row - col + cols.length - 1;
if(leftTop[ltIndex]) continue;
let rtIndex = row + col;
if(rightTop[rtIndex]) continue;
cols[col] = true;
leftTop[ltIndex] = true;
rightTop[rtIndex] = true;
place(row + 1);
cols[col] = false;
leftTop[ltIndex] = false;
rightTop[rtIndex] = false;
}
}
};
var totalNQueens = function(n) {
if(n < 1) return;
let count = 0;
// 数组索引是行号，数组元素是列号
let cols = new Array(n);
place(0);
return count;
function place(row) {
if(row === n) {
count++;
return;
}
for (let col = 0; col < n; col++) {
if(isValid(row, col)) {
// 在第row行第col列摆放皇后
cols[row] = col;
place(row + 1);
}
}
}
function isValid(row, col) {
for (let i = 0; i < row; i++) {
// 第col列已经有皇后
if(cols[i] === col) {
return false;
}
// 第i行的皇后跟第row行第col列格子处在同一斜线上
if(row - i === Math.abs(col - cols[i])) {
return false;
}
}
return true;
}
};
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
来源：leetcode-cn.com/problems/le…
var letterCombinations = function(digits) {
if(!digits) return [];
let phone = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
let ans = [], arr = [];
for (let digit of digits) {
arr.push(phone[digit])
}
let backtrace = (str = '', index = 0) => {
if(index === digits.length) {
ans.push(str)
} else {
for (let i of arr[index]) {
let tmp = str + i;
backtrace(tmp, index + 1)
}
}
}
backtrace()
return ans;
};
转载自:https://juejin.cn/post/6887049646988853262