回溯,就是无脑冲,碰壁之后就回撤一步继续搞,属于一种暴力解题的思路;
实际上也是如此,当我们在遇到一些分类讨论的问题,无法想到比较精妙的解决方案,我们第一时间考虑到的就是暴力枚举所有情况,然后再做处理,而 回溯
就是这样的一个暴力法
下一个 tab 学习一下常规的排序算法
吧
在做回溯题
的过程中,会发现很迷茫,因为很多题好像不需要返回,在执行下一步的过程中,我就做好判定,然后将可能的失败遏制住了,这个时候,一般能继续往下走的,都属于还行的操作,我们其实可以把这种方式叫做 剪枝
我一度陷入深思,是不是回溯就没用了呢,是不是只要脑瓜还行,其实剪枝就好了,还回溯啥,直到想起回溯的核心思想,它其实是一种暴力解法
, 也就是如果你能用其他方法,其实不用回溯
,是比较好的思路,一般情况下,回溯的复杂度会比较高
那么到底什么时候用回溯
呢?那种你没法子预设结局,或者说你的选择不单单关联相邻层的选择,而是会对更深层都有影响,比方说 51. N 皇后
我们需要求的是完整的棋盘,每一层的选择,都会影响整个棋盘的的布局,这个时候想在下棋那一刻就将全部可能情况想出来,太难了,这时候用回溯
就是很好的选择
而对于一些只与上层有影响,这个时候剪枝
也不失是一个好的选择;
其实在做系列总结的时候,会尽可能用系列的方法去解答,但是一题多解也是我们追求的,而且我们最后想要实现的,肯定是不局限与某写法,而是只要看到了,就能 a 出来;
所以努力将大部分常规的 tab 复习一遍,然后再慢慢填补,总结属于自己的解题方案,才是做总结的目的吧;
与大家一起努力呀
分析
var permute = function (nums) {
let ret = [];
const dfs = (arr, getIndex) => {
if (arr.length === nums.length) {
ret.push(arr);
return;
}
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (!!getIndex[i]) continue; // 如果存在,则代表已经有这个值了
getIndex[i] = 1;
dfs([...arr, num], getIndex);
getIndex[i] = 0;
}
};
const getIndexArr = new Array(nums.length)
dfs([], getIndexArr);
return ret;
};
分析
var permuteUnique = function(nums) {
const ret = []
const len = nums.length
nums.sort((a,b)=>a-b) // 排序
const dfs = (arr,indexArr) => {
if(arr.length === len ){
ret.push(arr)
return
}
for(let i = 0;i<len;i++){
if(!!indexArr[i]) continue
const num = nums[i]
indexArr[i] = 1
dfs([...arr,num],indexArr)
indexArr[i] = 0
// 回溯回来,如果下一个值一样,那么就是要重复走之前的老路了,所以还是直接跳过的好
while(nums[i+1]=== nums[i]) {
i++
}
}
}
dfs([],[])
return ret
}
console.log(permuteUnique([1,1,2]))
分析
无重复
,正整数数组参考视频:传送门
var combinationSum = function(candidates, target) {
const ret = []
const dfs = (start,arr,sum) => {
if(sum === target){
ret.push(arr)
return
}
if(sum>target) return
for(let i = start;i<candidates.length;i++){
// 因为允许重复取,所以每一次都是从 start 这个节点开始取的
dfs(i,[...arr,candidates[i]],sum+candidates[i])
}
}
dfs(0,[],0)
return ret
}
分析
有无重复
,正整数数组排序
var combinationSum2 = function (candidates, target) {
candidates.sort((a,b)=>a-b)
const ret= []
const dfs = (start,arr,sum) => {
if(sum === target) {
ret.push(arr)
return
}
if(sum>target || start>= candidates.length) return
for(let i = start;i<candidates.length;i++){
// 将重复的剪掉
if(i > start && candidates[i] === candidates[i-1]) continue
// 这里的 start 是启动枚举的下标,但是插入到临时数组的值是当前下标的值
dfs(i+1,[...arr,candidates[i]],sum+candidates[i])
}
}
dfs(0,[],0)
return ret
}
分析
无重复
,1-9 的正整数数组var combinationSum3 = function (k, n) {
const ret = [];
const dfs = (start, arr, sum) => {
if (arr.length === k && sum === n) {
ret.push(arr);
return;
}
if (arr.length > k || sum > n) {
return;
}
for (let i = start + 1; i < 10; i++) {
dfs(i, [...arr, i], sum + i);
}
};
dfs(0, [], 0);
return ret
};
分析 -- 回溯
无重复
,正整数数组,可以重复取值且要取排列不同
的组合var combinationSum4 = function (nums, target) {
let ret = 0;
const dfs = (sum) => {
if (sum === target) {
ret++;
return;
}
if (sum > target) return;
for (let i = 0; i < nums.length; i++) {
dfs(sum + nums[i]);
}
};
dfs(0);
return ret;
};
分析 -- dp
var combinationSum4 = function (nums, target) {
const dp = new Array(target+1)
dp[0]= 1 // 如果刚好得到的值是0,那么就有 1,因为不取也是一种取法
for(let i = 1;i<target+1;i++){
dp[i] = 0
for(let j =0;j<nums.length;j++){
if(i>=nums[j]){
dp[i]+=dp[i-nums[j]]
}
}
}
return dp[target]
}
分析 -- 找规律
var subsets = function (nums) {
let ret = [[]]
for(let num of nums ){
ret = [...ret,...ret.map(item => item.concat(num))]
}
return ret
}
分析 -- 迭代回溯
var subsets = function (nums) {
const ret = []
const dfs = (start,arr) => {
ret.push(arr)
if(arr.length === nums.length || start=== arr.length) return
for(let i = start;i<nums.length;i++){
dfs(i+1,[...arr,nums[i]])
}
}
dfs(0,[])
return ret
}
分析 -- 有重复值
var subsetsWithDup = function (nums) {
nums.sort((a,b)=> a-b)
const ret = []
const dfs = (start,arr) => {
ret.push(arr)
if(start === nums.length ) return // start 超出下标,就是取到了最大下标值的时候了
for(let i = start;i<nums.length;i++){
dfs(i+1,[...arr,nums[i]])
while(nums[i] === nums[i+1]){
i++ // 去重
}
}
}
dfs(0,[])
return ret
}
分析
var partition = function(s) {
const ret = []
// 判断是否是回文子串
function isValid(s) {
if(s.length === 1) return true // 只有一个字符
let l = 0,r = s.length-1
while(l<r){
if(s[l] !== s[r]) return false
l++
r--
}
return true
}
const dfs = (start,arr) => {
if(start === s.length){
ret.push(arr)
return
}
let temp =''
for(let i =start;i<s.length;i++){
temp+=s[i]
if(isValid(temp)){
dfs(i+1,[...arr,temp])
}
}
}
dfs(0,[])
return ret
};
分析
var restoreIpAddresses = function (s) {
const ret = [];
function isValid(s) {
if (s.length > 1 && s[0] == 0) return false; // 不能以 0 起头
if (s >= 1 << 8) return false; // 要在 [0,255] 之间
return true;
}
const dfs = (start, arr) => {
if (arr.length === 4 && start !== s.length) return; // 已经分成4分,但是还没分完
if (start === s.length) {
if (arr.length === 4) {
ret.push(arr.join("."));
}
// 无论是否分成四份,都离开了
return;
}
let str = "";
for (let i = start; i < s.length && i < start + 3; i++) {
str += s[i];
if (isValid(str)) {
dfs(i + 1, [...arr, str]);
}
}
};
dfs(0, []);
return ret;
};
分析
var hasPathSum = function(root, targetSum) {
let ret = false
const dfs = (root,sum) => {
if(ret || !root) return // 只要一条路走通了,其他都不用走了
sum += root.val
if(!root.left && !root.right && sum === targetSum) {
ret = true
return
}
if(root.left) dfs(root.left,sum)
if(root.right) dfs(root.right,sum)
}
dfs(root,0)
return ret
};
分析
var pathSum = function(root, targetSum) {
const ret = []
const dfs = (root,arr,sum) => {
if(!root) return
sum+=root.val
arr = [...arr,root.val]
if(!root.left && !root.right && sum == targetSum){
ret.push(arr)
}
if(root.left) dfs(root.left,[...arr],sum)
if(root.right) dfs(root.right,[...arr],sum)
}
dfs(root,[],0)
return ret
};
分析
起始-结束
节点,;var pathSum = function (root, targetSum) {
let ret = 0;
// 这是以任意 root 节点找路径和的 dfs
const dfs = (root, sum) => {
if (!root) return;
sum += root.val;
if (sum === targetSum) ret++;
if (!root.left && !root.right) return; // 叶子节点了,结束
if (root.left) dfs(root.left, sum);
if (root.right) dfs(root.right, sum);
};
// 这是遍历整棵树,然后继续往下走
const outer = (root) => {
if (!root) return;
dfs(root, 0);
outer(root.left);
outer(root.right);
};
outer(root);
return ret;
};
参考: leetcode-cn.com/problems/n-…
分析 -- 直接求符合要求的 chessboard
var solveNQueens = function (n) {
const ret = [];
// 1. N 皇后实际走的过程 -- 回溯树
const dfs = (row, chessboard) => {
if (row === n) {
// 已经到了叶子结点下 null 了 --
// 但是 chessboard 是一个二维数组,不能随便就push 进去的,需要深拷贝一下
ret.push(getStrChessboad(chessboard));
return;
}
// 每一行都是从 0 - n-1 , 然后不符合要求的就回溯回去
for (let col = 0; col < n; col++) {
if (isValid(row, col, chessboard)) {
// 如果 chessboard[row][col] 符合要求,则算一条路
chessboard[row][col] = "Q";
dfs(row + 1, chessboard);
chessboard[row][col] = "."; // 回溯回来
}
}
};
// 判断当前节点是否符合 N 皇后的要求 -- 需要注意,这里 [0,n-1] 是从左往右算
function isValid(row, col, chessboard) {
// 同一列
for (let i = 0; i < row; i++) {
if (chessboard[i][col] === "Q") {
return false;
}
}
// 从左往右 45` 倾斜
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] === "Q") {
return false;
}
}
// 从右往左 135` 倾斜
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] === "Q") {
return false;
}
}
// 如果不是同一列或者左右斜线,则满足要求
return true;
}
// 将二维数组的 N 皇后转成一维数组字符串形式
function getStrChessboad(chessboard) {
const ret = [];
chessboard.forEach((row) => {
let str = "";
row.forEach((item) => {
str += item;
});
ret.push(str);
});
return ret;
}
const chessboard = new Array(n).fill([]).map(() => new Array(n).fill("."));
dfs(0, chessboard);
return ret;
};
分析
var totalNQueens = function (n) {
let ret = 0;
const dfs = (row, chessboard) => {
if (row === n) {
ret++;
return;
}
for (let col = 0; col < n; col++) {
if (isValid(row, col, chessboard)) {
chessboard[row][col] = "Q";
dfs(row + 1, chessboard);
chessboard[row][col] = ".";
}
}
function isValid(row, col, chessboard) {
for (let i = 0; i < row; i++) {
if (chessboard[i][col] === "Q") return false;
}
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] === "Q") return false;
}
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] === "Q") return false;
}
return true;
}
};
const chessboard = new Array(n).fill([]).map(() => new Array(n).fill("."));
dfs(0, chessboard);
return ret;
};
@分析
的值, 从右启动的 135
的值var totalNQueens = function (n) {
let ret = 0;
const dfs = (r, col, dlr, drl) => {
if (r === n) {
ret++;
return;
}
for (let i = 0; i < n; i++) {
// 当前坐标转成二进制位对应的值
const _col = 1 << i;
const _dlr = 1 << (r + i); // 这里表示在其他行 的 i 值,到了当前 r,对应的值就应该是 1 << (r+i), 所以我们设置这么一个值去试其他的值,看看是否满足要求
const _drl = 1 << (n - i + r);
if ((col & _col) || (dlr & _dlr) || (drl & _drl)) continue; // 只要有一个为 true,
dfs(r + 1, col | _col, dlr | _dlr, drl | _drl);
}
};
dfs(0, 0, 0, 0);
return ret;
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。