回溯算法

回溯算法基本理论

是什么：

回溯采用是错得方法解决问题，一旦发现当前步骤失败，回溯算法就会返回上一个步骤

解决哪些问题：

组合问题（组合不强调顺序，而排列强调）
切割问题
子集问题
排列问题
棋盘问题

如何理解回溯法

回溯法都可以抽象为一个树形结构。一个n叉树

图 0

回溯法的模板

// 递归函数没有返回值
void backtrading(参数){
  // 递归终止条件
  if (终止条件){ //通常在叶子节点
    //收集结果
    return
  }
  // 单层搜索
  for (集合得元素集){ //遍历集合中的每一个元素
    // 处理节点
    // 递归函数
    // 回溯
  }
  return
}

回溯算法剪枝

剪枝一般都是在for循环的i的范围上做文章，例如下面的组合题目，确定i至多从哪里开始。
图 4

回溯算法题目

组合问题

题目：https://leetcode.cn/problems/combinations/description/

图 2

未剪枝

var combine = function(n, k) {
  var path = [];  // 用来存放每一个结果
  var res = [];  //存放所有结果的数组
  //确定参数
  const backTrading = (n, k, startIndex) => { //startIndex搜索的起始位置
    //终止条件
    if(path.length === k){
      //注意这里要深拷贝一下path，因为path是引用类型，后续的操作会改变path的值
      res.push([...path]); //将path的值push到res中
      return;
    }
    // 单层递归逻辑
    for(let i = startIndex; i <= n; i++){
      path.push(i);
      backTrading(n, k, i + 1); //递归,起始位置+1
      path.pop(); //回溯的过程，弹出最后一个元素
    }
  }
  backTrading(n, k, 1); //调用backTrading函数,第一次竟然忘了这一步
  return res;
};

剪枝

// path.length 已选取的元素的大小
// k-path.length 还需要的元素
// n-(k-path.length)+1 i的至多从该位置开始取
var combine = function(n, k) {
  var path = [];  // 用来存放每一个结果
  var res = [];  //存放所有结果的数组
  //确定参数
  const backTrading = (n, k, startIndex) => { //startIndex搜索的起始位置
    //终止条件
    if(path.length === k){
      //注意这里要深拷贝一下path，因为path是引用类型，后续的操作会改变path的值
      res.push([...path]); //将path的值push到res中
      return;
    }
    // 单层递归逻辑
    //剪枝在for循环停止的位置做文章
    for(let i = startIndex; i <= (n-(k-path.length)+1); i++){
      path.push(i);
      backTrading(n, k, i + 1); //递归,起始位置+1
      path.pop(); //回溯的过程，弹出最后一个元素
    }
  }
  backTrading(n, k, 1); //调用backTrading函数,第一次竟然忘了这一步
  return res;
};

组合总和 III

https://leetcode.cn/problems/combination-sum-iii/description/

图 5

图 6

//加了剪枝操作
var combinationSum3 = function(k, n) {
  let path = []   //一维数组，用来存放符合条件的组合
  let res = []    //二维数组，用来存放符合条件的组合数组
  const backTrading = (n,k,sum,startIndex)=>{ //sum是当前path数组的和
    if(sum>n) return  //这是一个剪枝操作
    if(path.length ===k){
      if(sum === n){
        res.push([...path])
      }
      return
    }
  // i的边界的控制也是剪枝操作
  for(let i = startIndex;i<=(9-(k-path.length)+1);i++){
    sum += i
    path.push(i)
    backTrading(n,k,sum,i+1) //这里是深入分支
    sum -= i    //回溯，这里是广度的遍历，挨个遍历每一个元素
    path.pop()
  }
}
  backTrading(n,k,0,1)
  return res
};

电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

解题思路

先做数字和字母的映射
通过树形结构梳理思路

图 7

var letterCombinations = function(digits) {
  //先做一个映射表
  const map = new Map()
  map.set('2','abc')
  map.set('3','def')
  map.set('4','ghi')
  map.set('5','jkl')
  map.set('6','mno')
  map.set('7','pqrs')
  map.set('8','tuv')
  map.set('9','wxyz')
  let str = ''   //收获单个结果
  let res = []
  const backTrading = (digits,index)=>{
    if(!digits) return
    if(index === digits.length){  //终止条件
      res.push(str)
      return
    }
    //单层逻辑
    let digit = digits[index]  //找到数字
    let letters = map.get(digit)   // 根据数字在映射表中找到对应的字母
    for(let i=0;i<letters.length;i++){
      str += letters[i]
      backTrading(digits,index+1)
      str = str.slice(0,str.length-1) //回溯
    }
  }
  backTrading(digits,0)
  return res
};

组合总和

https://leetcode.cn/problems/combination-sum/description/

数组中没有0且没有重复数字。

图 8

var combinationSum = function(candidates, target) {
  //递归终止条件
  let path = []
  let res = []
  const backTraking = (candidates,target,sum,startIndex)=>{
    if (sum > target) return
    if (sum === target) {
      res.push(path.slice())  //深拷贝
      return
    }
    for(let i = startIndex;i<candidates.length;i++){
      path.push(candidates[i])
      sum += candidates[i]
      backTraking(candidates,target,sum,i) //可以重复i不加1喽
      sum -= candidates[i]
      path.pop()
    }
  }
  backTraking(candidates,target,0,0)
  return res
};

剪枝
图 9

var combinationSum = function(candidates, target) {
  //递归终止条件
  let path = []
  let res = []
  const backTraking = (candidates,target,sum,startIndex)=>{
    // if (sum > target) return
    if (sum === target) {
      res.push(path.slice())  //深拷贝
      return
    }
    for(let i = startIndex;i<candidates.length;i++){
      if (candidates[i] + sum > target) continue; //剪枝
      path.push(candidates[i])
      sum += candidates[i]
      backTraking(candidates,target,sum,i) //可以重复i不加1喽
      sum -= candidates[i]
      path.pop()
    }
  }
  backTraking(candidates,target,0,0)
  return res
};

组合总和 II

https://leetcode.cn/problems/combination-sum-ii/description/

难点在于：结果中不能有重复的结果[1,7],[7,1]。但是能原数组中有两个1，有可以有[1,1,6]。

图 10

树层去重和树枝去重

https://www.programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#%E6%80%9D%E8%B7%AF

var combinationSum2 = function(candidates, target) {
  let path = []
  let res = []
  // 进行排序
  candidates.sort((a,b)=>a-b)
  const backTracking = (candidates,target,sum,startIndex,used)=>{
    if (sum === target){
      res.push(path.slice())
      return
    }
    for(let i = startIndex;i<candidates.length;i++){
      if (sum + candidates[i] > target) continue  //剪枝
      // i>0是为了保证i-1有意义
      // used[i-1]=false，说明此时处于树层的状态，即同一树层上的前一个元素已经被撤销，所以此时可以继续使用
      if (i > 0 && candidates[i] === candidates[i-1] && !used[i-1]) continue  //数层去重的而过程，前提是数组有序
      path.push(candidates[i])
      sum += candidates[i]
      used[i] = true  //标记使用过
      backTracking(candidates,target,sum,i+1,used)
      //回溯
      sum -= candidates[i]
      path.pop()
      used[i] = false
    }
  }
  backTracking(candidates,target,0,0,new Array(candidates.length).fill(false))
  return res
};

分割回文子串

https://leetcode.cn/problems/palindrome-partitioning/description/

图 11

难点：

切割问题和组合是一样的，之前选择的元素下标，相当于这里的切割线
如何表示切割的字串[startIndex,i]

var partition = function(s) {
  let path = [] //一维数组，用来存放每一次的结果
  let res = [] //二维数组，用来存放所有的结果、
  const backTraking = (s,startIndex)=>{
    if(startIndex >= s.length){  //到了叶子就节点了，将结果放入res中
      res.push(path.slice())
      return
    }
    // 单层搜索逻辑
    for(let i=startIndex;i<s.length;i++){
      // 如果是回文子串，才添加到path中，否则直接continue
      if(isPlalindrome(s,startIndex,i)){
        path.push(s.substring(startIndex,i+1))
        backTraking(s,i+1)
        path.pop()
      }
    }
  }
  const isPlalindrome = (s,left,right)=>{
    //判断是否是回文串的函数
    while(left<right){
      if(s[left] !== s[right]) return false
      left++
      right--
    }
    return true
  }
  backTraking(s,0)
  return res
};

复原IP地址

https://leetcode.cn/problems/restore-ip-addresses/description/

合法的IP地址：有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

图 12

var restoreIpAddresses = function(s) {
  let path = []
  let res = []
  const backTracking = (s,startIndex)=>{
    if(path.length === 4 && startIndex === s.length){
      res.push(path.join('.'))
      return
    }
    //剪枝了，如果path的长度已经是4了，但是startIndex还没有到s的长度，那么就不用再继续了
    if(path.length === 4 && startIndex < s.length) return
    // 剪枝了，如果path的长度不是4了，但是startIndex已经到s的长度了，那么也不用再继续了
    for(let i= startIndex;i<s.length && i<= startIndex+3;i++){
      if (isValid(s,startIndex,i)){
        path.push(s.substring(startIndex,i+1))
        backTracking(s,i+1)
        path.pop()
      }
    }
  }
  const isValid = (s,startIndex,i)=>{
    if(s[startIndex] === '0' && i !== startIndex) return false
    if(parseInt(s.substring(startIndex,i+1)) > 255) return false
    return true
  }
  backTracking(s,0)
  return res
};

前面的一系列都是在叶子节点收获结果，终止条件的写法基本一致

后面开始要从每一个节点收获结果，终止条件的写法发生变化。

子集

https://leetcode.cn/problems/subsets/description/

图 13

var subsets = function(nums) {
  let path = []
  let res = []
  const backTraking = (nums,startIndex)=>{
    // 每个节点都收获一次、如果终止条件改为>，这一句要放在if的下面，单层搜索逻辑的上面。
    res.push([...path])
    //终止条件是，到了叶子节点
    if(startIndex >= nums.length){
      return //剩余元素为空时，也就是startIndex到达了nums的长度
    }

    for(let i=startIndex;i<nums.length;i++){
      path.push(nums[i])
      backTraking(nums,i+1)
      path.pop()
    }
  }
  backTraking(nums,0)
  return res
};

子集II

树层去重：确定当前在树层used[i-1]===fasle,当前元素与前一元素相等，i>0

https://leetcode.cn/problems/subsets-ii/description/

图 14

var subsetsWithDup = function(nums) {
  let path = []
  let res = []
  used = new Array(nums.length).fill(false)
  // 排序
  nums.sort((a, b) => a - b)
  const backTraking = (nums, startIndex, used) => {
    res.push([...path])
    if (startIndex >= nums.length) {
      return
    }
    for (let i = startIndex; i < nums.length; i++) {
      // i>0是为了保证i-1有意义
      // used[i-1]=false，说明此时处于树层的状态，即同一树层上的前一个元素
      // 已经被撤销，所以此时可以继续使用
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue
      }
      path.push(nums[i])
      used[i] = true
      backTraking(nums, i + 1, used)
      path.pop()
      used[i] = false
    }
  }
  backTraking(nums, 0, used)
  return res
};

递增子序列

https://leetcode.cn/problems/non-decreasing-subsequences/

去重方法：由于不能排序，所以这里的树层去重和之前有所差别
之前的题目基本使用used来记录事都使用过某一元素，因为是有序的，只需判断used[i-1] ，nums[i-1]===nums[i]
现在得到题目是无序的，使用set，每次循环判断当前数字是否在set中，如果在，跳过，否则将数字放入set，实现去重。

var findSubsequences = function(nums) {
  let path = []
  let res = []
  // 回溯算法函数
  const backTraking = (nums,startIndex)=>{
    // 收获结果的地方
    if (path.length > 1){
      res.push([...path])
    }
    // 终止条件
    if (startIndex >= nums.length){
      return
    }
    //单层搜索逻辑
    let set = new Set()
    for(let i=startIndex;i<nums.length;i++){
      // 当前元素小于path最后的元素，跳过. 但是如果path为空，不跳过
      if (nums[i] < path[path.length-1] || !path ){
        continue
      }
      // 树层去重
      if(set.has(nums[i])){
        continue
      }
      else{
        set.add(nums[i])
      }
      path.push(nums[i])
      backTraking(nums,i+1)
      path.pop()
    }
  }
  backTraking(nums,0)
  return res
};

全排列

https://leetcode.cn/problems/permutations/description/

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
图 15

var permute = function(nums) {
  let path =[]
  let res = []
  let used = new Array(nums.length).fill(false)
  const backTracking = (nums)=>{
    if(path.length === nums.length){
      res.push([...path])
      return
    }
    for(let i=0; i<nums.length; i++){
      if(used[i]){
        continue
      }
      used[i] = true
      path.push(nums[i])
      backTracking(nums)
      path.pop()
      used[i] = false
    }
  }
  backTracking(nums)
  return res
};

全排列II

https://leetcode.cn/problems/permutations-ii/description/

加一个数层去重

var permuteUnique = function(nums) {
  let path = []
  let res = []
  // 用于排列
  let used = new Array(nums.length).fill(false)
  // 用于数层去重
  let used1 = new Array(nums.length).fill(false)
  nums.sort((a,b)=>a-b)
  const backTracking = (nums)=>{
    // 终止条件
    if(path.length === nums.length){
      res.push([...path])
      return
    }
    for(let i=0; i<nums.length; i++){
      if (used[i]){
        continue
      }
      //树层去重
      if(i>0 && nums[i] === nums[i-1] && !used1[i-1]){
        continue
      }
      used[i] = true
      used1[i] = true
      path.push(nums[i])
      backTracking(nums)
      path.pop()
      used[i] = false
      used1[i] = false
    }
  }
  backTracking(nums)
  return res
};

重新安排行程

https://leetcode.cn/problems/reconstruct-itinerary/description/

N皇后

https://leetcode.cn/problems/n-queens/

图 16

var solveNQueens = function(n) {
  let res = []
  // Array.from() 是一个静态方法，它从类数组或可迭代对象创建一个新的数组实例。
  let checkboard = Array.from({length:n},()=>Array.from({length:n},()=>'.'))
  const isVaild = (row,col,checkboard,n)=>{
    // 检查列,只需要检查当前行上面的行
    for(let i=0;i<row;i++){
      if(checkboard[i][col] === 'Q'){
        return false
      }
    }
    // 检查左上方45度对角线
    for(let i= row-1,j=col-1;i>=0 && j>=0;i--,j--){
      if(checkboard[i][j] === 'Q'){
        return false
      }
    }
    // 检查右上方45度对角线
    for(let i=row-1,j=col+1;i>=0 && j<n;i--,j++){
      if(checkboard[i][j] === 'Q'){
        return false
      }
    }
    return true
  }

  const backTraking = (checkboard,n,row)=>{
    if(row==n){
      res.push(checkboard.map(row=>row.join('')))
      return
    }
    for (let col=0;col<n;col++){
      //判断放在这里是否符合要求
      if (isVaild(row,col,checkboard,n)){
        checkboard[row][col] = 'Q'
        backTraking(checkboard,n,row+1)
        checkboard[row][col] = '.'
      }
    }
  }
  backTraking(checkboard,n,0)
  return res
};

解数独

https://leetcode.cn/problems/sudoku-solver/
https://www.programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

var solveSudoku = function (board) {
  function isValid(row, col, val, board) {
    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
      }
    }
    // 3*3的格子不能重复
    let startRow = Math.floor(row / 3) * 3 // 0,3,6
    let startCol = Math.floor(col / 3) * 3 // 0,3,6

    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++) {
          if (isValid(i, j, `${val}`, board)) {
            board[i][j] = `${val}`
            if (backTracking()) {
              return true
            }

            board[i][j] = `.`
          }
        }
        return false
      }
    }
    return true
  }
  backTracking(board)
  return board
};