回溯算法及题目
题号 |
题目 |
Tag |
39 |
组合总和 |
数组、回溯算法 |
40 |
组合总和II |
数组、回溯算法 |
46 |
全排列 |
数组、回溯算法 |
51 |
N皇后 |
数组、回溯算法 |
墙裂推荐这篇文章:回溯算法解题套路框架
下面内容大多参考上面这篇文章,对其作者labuladong表示感谢。
回溯算法的框架
解决一个回溯问题,实际上就是一个决策树的遍历过程。 只需要思考3个问题:
- 路径:也就是已经做出的选择
- 选择列表:也就是当前可以做的选择
- 结束条件:也就是到达决策树底层,无法再做选择的条件。
在后面的题目中会对这个三个词语再进行解释。
代码方面,回溯算法的框架:
1 2 3 4 5 6 7 8 9 10 11 12 13
| let res = []; function backtrack(路径, 选择列表) { if(满足结束条件) { res.add(路径); return; } for (let 选择 in 选择列表) { 做选择 backtrack(路径, 选择列表) 撤销选择 } }
|
其核心就是for循环里面的递归,在递归之前「做选择」,在递归之后「撤销选择」. 关于做选择和撤销选择,先通过全排列这个问题来了解一下。
全排列
我们知道n个不重复的数,全排列共有n!个。
为了简单清晰起见,这次只考虑全排列问题不包含重复的数字。
那么我们当时是怎么穷举全排列的呢?比方说给三个数 [1,2,3],你肯定不会无规律地乱穷举,一般是这样:
先固定第一位为 1,然后第二位可以是 2,那么第三位只能是 3;然后可以把第二位变成 3,第三位就只能是 2 了;然后就只能变化第一位,变成 2,然后再穷举后两位……
其实这就是回溯算法,我们高中无师自通就会用,或者有的同学直接画出如下这棵回溯树:
只要从根遍历这棵树,记录路径上的数字,其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。
为啥说这是决策树呢,因为你在每个节点上其实都在做决策。 比如你站在下图的红色节点上:
你现在就在做决策,可以选择 1 那条树枝,也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢?因为 2 这个树枝在你身后,这个选择你之前做过了,而全排列是不允许重复使用数字的。
现在就可以解答开头的几个名词:[2]就是「路径」,[1,3]就是「选择列表」,表示你当前可以做出的选择;「结束条件」就是遍历到树的底层,在这里就是选择列表为空的时候。
我们定义的backtrack函数其实就像一个指针,在这棵树上游走,同时要正确维护每个节点的属性,每当走到树的底层,其「路径」就是一个全排列。
所以说for循环里面的递归就是回溯算法的关键:
1 2 3 4 5 6
| for 选择 in 选择列表 路径.push(选择) backtrack(路径,选择列表) 路径.pop(选择)
|
我们只要在递归之前做出选择,在递归之后撤销刚才的选择,就可以正确地得到每个节点的选择列表和路径。
46、全排列代码:
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 35 36 37 38 39 40 41 42 43 44 45
|
var permute = function (nums) { let res = [], track = []; if (nums.length == 0) return []; backtrack(track);
function backtrack(track) { if (track.length == nums.length) { res.push(track.slice()); return; } for (let i = 0; i < nums.length; i++) { if (track.includes(nums[i])) continue; track.push(nums[i]); backtrack(track); track.pop(); } }
return res; };
|
我们这里稍微做了些变通,没有显式记录「选择列表」,而是通过 nums 和 track 推导出当前的选择列表:判断track.includes(nums[i])。
39、组合总和
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
var combinationSum = function (candidates, target) { let res = [], track = []; candidates.sort((a, b) => a - b);
function backtrack(target, track, start) { if(target == 0) { res.push(track.slice()); return; } for(let i = start; i < candidates.length; i++) { if(target < candidates[i]) break; track.push(candidates[i]); backtrack(target - candidates[i], track, i); track.pop(); } }
backtrack(target, track, 0);
return res; }
|
40、组合总和II
这个和第39题的不同之处在于,数组中的元素可以重复, 并且每个数字在每个组合中只能使用一次。
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
|
var combinationSum2 = function (candidates, target) { let res = [], track = []; candidates.sort((a, b) => a - b);
function backtrack(target, track, start) { if(target == 0) { res.push(track.slice()); return; } for(let i = start; i < candidates.length; i++) { if(i - start > 0 && candidates[i - 1] == candidates[i]) continue; if(target < candidates[i]) break; track.push(candidates[i]); backtrack(target - candidates[i], track, i + 1); track.pop(); } }
backtrack(target, track, 0); return res; }
|
51、N皇后
ps:皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一到七步,可进可退。
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
var solveNQueens = function (n) { let res = [], board = []; for(let i = 0; i < n; i++) { board[i] = new Array(n).fill('.'); }
function backtrack(board, row) { if(row == board.length) { res.push(JSON.parse(JSON.stringify(board))); return; } for(let column = 0; column < board.length; column++) { if(!isValid(board, row, column)) continue; board[row][column] = 'Q'; backtrack(board, row + 1); board[row][column] = '.'; } }
function isValid(board, row, column) { for(let m = 0; m < board.length; m++) { if(board[m][column] == 'Q') return false; } for(let m = row - 1, n = column + 1; m >= 0 && n < board.length; m--, n++) { if(board[m][n] == 'Q') return false; } for(let m = row - 1, n = column - 1; m >= 0 && n >= 0; m--, n--) { if(board[m][n] == 'Q') return false; } return true; }
backtrack(board, 0); return res.map(item => { return item.map(subitem => subitem.join('')); });; }
|
最后
回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,算法框架如下:
1 2 3 4 5 6
| for (let 选择 in 选择列表) { 做选择 backtrack(路径, 选择列表) 撤销选择 }
|
写backtrack函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集。