study-notes回溯算法
回溯算法并不是高效的算法，最多再剪枝一下，有回溯就会有递归
回溯算法能解决的问题
- 组合问题：N个数里面按一定规则找出k个数的集合
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 棋盘问题：N皇后，解数独等等
回溯算法的模板
javascript
const backtracking = (参数)=>{
//此处是收集满足条件的叶子节点或者节点（子集问题）
if(终止条件){
存放结果;
retrun;
}
for(遍历集合){
合理的条件下 处理节点;
backtracking()//递归;
回溯，撤销处理结果
}
}
组合问题
什么时候需要startIndex？例如求一个集合的组合的话就需要，而多个集合取组合，各个集合之间互相不受影响，那么就不用startIndex
单集合求组合
对于path长度有限制或者path里的元素有限制，都放在终止条件
对于去重问题，可以使用
排序+used数组javascript//升序 arr.sort((a,b)=>a-b); //used数组 const len = arr.length; const used = new Array(len).fill(false); //在arr中，前一个数和后一个数相同的情况下(arr[i] == arr[i - 1])： //used[i - 1] == true，说明同一树枝arr[i - 1]使用过 //used[i - 1] == false，说明同一树层arr[i - 1]使用过
多集合求组合
多集合求组合，各个集合之间互相不受影响，不需要startIndex
- 需要一个index取出元素对应的集合
切割问题
切割问题应该运用求解组合问题的思路去解决，特别是注意如何合法切割和终止条件，
分割问题通常也需要startIndex
- 切割问题最重要的就是合法切割
子集问题
与组合问题不同，子集问题是收集满足条件的所有节点结果
注意子集问题，收集结果直接放在前面
子集问题也要startIndex
对于解集不能包含重复的子集，用
排序和used数组去重对于题目不能要求排序的，但是又要求去重的，可以在每层使用
set去重，例如递增子序列
排列问题
排列问题与组合类问题大不相同，处理排列问题不需要startIndex了
- 使用
排序+used数组对同一层、同一树枝进行限制（去重） for循环索引值从0开始
棋盘问题
除了使用回溯，最最最重要的是编写isValid
N皇后
- N皇后处理核心是
isValid和回溯
javascript
var solveNQueens = function(n) {
// init chessBord
const chessBord = new Array(n).fill().map(x=> Array(n).fill('.'));
const res = [];
const isValid = (row,col)=>{
for(let i = 0;i < row;++i){//之前的行
for(let j = 0;j < n;++j){//所有的列
//发现Q，并且是在同一列或者对角线(不合法)
if(chessBord[i][j]==='Q' && (j===col || i+j === row+col || i-j === row-col)){
return false;
}
}
}
return true
}
const backtracking = (row)=>{
if(row === n){
//处理
//复制一份
const chessBordCopy = chessBord.slice();
for(let i = 0;i < n;++i){
//转换成字符串
chessBordCopy[i] = chessBordCopy[i].join('')
}
res.push(chessBordCopy);
return;
}
for(let col = 0;col < n;++col){
//如果合法
if(isValid(row,col)){
chessBord[row][col] = 'Q';
//递归
backtracking(row+1);
//回溯
chessBord[row][col] = '.';
}
}
}
backtracking(0);
return res;
};
解数独
javascript
var solveSudoku = function(board) {
//非常重要
function isValid(row, col, val) {
let len = board.length
// 行中的数字不能重复
for(let i = 0; i < len; i++) {
if(board[row][i] === val) {
return false
}
}
// 列中的数字不能重复
for(let i = 0; i < len; i++) {
if(board[i][col] === val) {
return false
}
}
//f
let startRow = Math.floor(row / 3) * 3
let startCol = Math.floor(col / 3) * 3
//方块中的数字不能重复
for(let i = startRow; i < startRow + 3; i++) {
for(let j = startCol; j < startCol + 3; j++) {
if(board[i][j] === val) {
return false
}
}
}
return true
}
function backTracking() {//回溯函数
for(let i = 0; i < board.length; i++) {
for(let j = 0; j < board[0].length; j++) {//循环行和列
if(board[i][j] !== '.') continue
for(let val = 1; val <= 9; val++) {//尝试在当前单元格放置1-9
if(isValid(i, j, `${val}`)) {//判断放置数字的合法性
board[i][j] = `${val}`//放置数字
if (backTracking()) {//合法返回ture
return true
}
board[i][j] = `.`//不合法回溯状态
}
}
return false//1-9的数字都不合法，返回false
}
}
return true//全部可能性都尝试完成 返回true 说明有解
}
backTracking()
return board
};