理论知识

回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。

终止：树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
遍历：回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯框架

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

强调的是去重一定要对元素经行排序，这样我们才方便通过相邻的节点来判断是否重复使用了

练习

77. 组合

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。

let result = []; //存放最终结果
let path = []; // 存放每次组合结果
var combine = function(n, k) {
    result = [];
    backTrack(n,k,1);
    return result;
};
function backTrack(n,k,startIndex){
    //1. 确定终止条件 这里是当path的length === k的时候 说明子集大小为k了
    if(path.length === k){
        result.push([...path]);
    }
    //2. 单层搜索过程 for横向遍历 startIndex确定取值位置
    for(let i=startIndex;i<= n; i++){
        path.push(i); // 处理节点
        backTrack(n,k,i+1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
        path.pop(); // 回溯 撤销已经处理过的节点
    }
    // 剪枝  最后k - len(path)个节点直接构造结果，无需递归
    // for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
    //     path.push(i)
    //     backTrack(n, k, i + 1)
    //     path.pop()
    // }
}

从这里可以看出来：回溯就一种比较暴力的搜索方法（不断的for循环迭代）

216. 组合总和 III

let result = [];
let path = [];
var combinationSum3 = function (k, n) {
  if (k > 9 || k < 1) return [];
  // result = [];
  backTrack(k, n, 1);
  return result;
};
function backTrack(k, n, startIndex) {
  if (sum(path) === n && path.length === k) {
    result.push([...path]);
    return;
  }
  for (let i = startIndex; i <= 9; i++) {
    path.push(i);
    backTrack(k, n, i + 1);
    path.pop();
  }
}
function sum(arr) {
  return arr.reduce((pre, cur) => pre + cur, 0);
}

let result = [];
let path = [];
var combinationSum3 = function (k, n) {
  if (k > 9 || k < 1) return [];
  result = [];
  backTrack(k, n, 1);
  return result;
};
function backTrack(k, n, startIndex) {
  if (n === 0 && k === 0) {
    result.push([...path]);
    return;
  }
  for (let i = startIndex; i <= 9; i++) {
    path.push(i);
    backTrack(k - 1, n - i, i + 1);
    path.pop();
  }
}

17. 电话号码的字母组合

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
/**
 * @param {string} digits
 * @return {string[]}
 */
//分析
                        root
                    /     |      \
level 0  '2'       a      b       c
                  /|\    /|\     /|\
level 1  '3'    ad ae af bd be bf cd ce cf
const TEL_DIGIT_MAP = {
  2: 'abc',
  3: 'def',
  4: 'ghi',
  5: 'jkl',
  6: 'mno',
  7: 'pqrs',
  8: 'tuv',
  9: 'wxyz',
};
let result = [];
let path = [];
var letterCombinations = function (digits) {
  if (digits.length === 0) return [];
  let n = digits.length;
  result = [];
  backTrack(digits, 0);
  return result;
};
function backTrack(digits, level) {
  if (level >= digits.length) {
    result.push(path.join(''));
    return;
  }
  const chars = TEL_DIGIT_MAP[digits[level]];
  for (let i = 0; i < chars.length; i++) {
    path.push(chars[i]);
    backTrack(digits, level + 1);
    path.pop();
  }
}

39. 组合总和

let result = [];
let path = [];

var combinationSum = function (candidates, target) {
  result = [];
  if (candidates == null || candidates.length == 0 || target < 0) return result;
  candidates.sort();
  backTrack(candidates, target, 0);
  return result;
};
function backTrack(candidates, target, start) {
  if (target === 0) {
    result.push([...path]);
  } else if (target > 0) {
    for (var i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      backTrack(candidates, target - candidates[i], i);//***注意：因为是可以重复选择元素 所以i不加1
      path.pop();
    }
  }
}

40. 组合总和 II

思路：

1. used
2. set
3. startIndex

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

// used[i - 1] == true，说明同一树支candidates[i - 1]使用过     
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过     
// 要对同一树层使用过的元素进行跳过

let result = [];
let path = [];
var combinationSum2 = function (candidates, target) {
  result = [];
  if (!candidates.length || !candidates || target < 0) return result;
  candidates.sort();
  backTrack(candidates, target, 0, {});
  return result;
};

function backTrack(candidates, target, startIndex) {
  if (target == 0) {
    result.push([...path]);
  } else {
    for (let i = startIndex; i < candidates.length; i++) {
      // 要对同一树层使用过的元素进行跳过
      if (i > startIndex && candidates[i] == candidates[i - 1]) {
        continue;
      }
      path.push(candidates[i]);
      backTrack(candidates, target - candidates[i], i + 1);
      path.pop();
    }
  }
}

let result = [];
let path = [];
var combinationSum2 = function (candidates, target) {
  result = [];
  if (!candidates.length || !candidates || target < 0) return result;
  candidates.sort();
  backTrack(candidates, target, 0, {});
  return result;
};

function backTrack(candidates, target, startIndex) {
  const set = new Set();
  if (target == 0) {
    result.push([...path]);
  } else {
    for (let i = startIndex; i < candidates.length; i++) {
      if (!set.has(candidates[i])) {
        path.push(candidates[i]);
        backTrack(candidates, target - candidates[i], i + 1);
        path.pop();
        set.add(candidates[i]);
      }
    }
  }
}

131. 分割回文串 ???

let result = [];
let path = [];
var partition = function (s) {
  result = [];
  if (s.length === 0) return result;
  backTrack(s, 0);
  return result;
};
function backTrack(s, startIndex) {
  // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
  if (startIndex >= s.length) {
    result.push([...path]);
    return;
  }
  for (let i = startIndex; i < s.length; i++) {
    if (!isPalindrome(s, startIndex, i)) continue;
    path.push(s.substr(startIndex, i - startIndex + 1)); // 获取[startIndex,i]在s中的子串
    backTrack(s, i + 1);
    path.pop();
  }
}

const isPalindrome = (s, l, r) => {
  for (let i = l, j = r; i < j; i++, j--) {
    if (s[i] !== s[j]) return false;
  }
  return true;
};

78. 子集

let path = [];
var subsets = function (nums) {
  result = []
  backTrack(nums, 0);
  return result;
};

function backTrack(nums, startIndex) {
  result.push([...path]);
  for (let i = startIndex; i < nums.length; i++) {
    path.push(nums[i]);
    backTrack(nums, i + 1);
    path.pop();
  }
}

90. 子集 II

let result = [];
let path = [];
var subsetsWithDup = function (nums) {
  nums.sort();
  backTrack(nums, 0, []);
  return result;
};

function backTrack(nums, startIndex, used) {
  result.push([...path]);
  if (startIndex > nums.length - 1) {
    return;
  }

  for (let i = startIndex; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
      continue;
    }
    used[i] = true;
    path.push(nums[i]);
    backTrack(nums, i + 1, used);
    path.pop();
    used[i] = false;
  }
}

let result = [];
let path = [];
var subsetsWithDup = function (nums) {
  nums.sort();
  backTrack(nums, 0);
  return result;
};

function backTrack(nums, startIndex) {
  result.push([...path]);
  if (startIndex > nums.length - 1) {
    return;
  }

  for (let i = startIndex; i < nums.length; i++) {
    if (i > startIndex && nums[i] === nums[i - 1]) {
      continue;
    }
    path.push(nums[i]);
    backTrack(nums, i + 1);
    path.pop();
  }
}

46. 全排列

• 每层都是从0开始搜索而不是startIndex
• 需要used数组记录path里都放了哪些元素了

var permute = function(nums) {
    const res = [], path = [];
    backtrack(nums,[]);
    return res;

    function backtrack(n, used) {
        if(path.length === n.length) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < n.length; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtrack(n,used);
            path.pop();
            used[i] = false;
        }
    }
};

47. 全排列 II

var permuteUnique = function (nums) {
    nums.sort((a,b)=> a-b);
    let result = []
    let path = []

    function backtracing(used) {
        if (path.length === nums.length) {
            result.push(path.slice())
            return
        }
        for (let i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                continue
            }
            if (!used[i]) {
                used[i] = true
                path.push(nums[i])
                backtracing(used)
                path.pop()
                used[i] = false
            }
        }
    }
    backtracing([])
    return result
};

491. 递增子序列 ???

51. N 皇后

约束条件：

1. 不能同行
2. 不能同列
3. 不能同斜线

• 棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了
• 每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
• 树的深度用row来代替，广度用col来替代

当前一行已经落下一个皇后之后，下一行需要判断三个条件：

1. 在这一列上，之前不能摆放过皇后。
2. 在对角线 1，也就是「左下 -> 右上」这条对角线上，之前不能摆放过皇后。
3. 在对角线 2，也就是「右上 -> 左下」这条对角线上，之前不能摆放过皇后。

var solveNQueens = function (n) {
  //1.根据n画棋盘 并且用.来填充
  const borad = new Array(n).fill([]).map(() => new Array(n).fill('.'));

  //2.判断皇后之间是否攻击
  function isValid(row, col, borad, n) {
    // 判断同列是否有冲突
    for (let i = 0; i < row; i++) {
      if (borad[i][col] === 'Q') {
        return false;
      }
    }
    // 判断45度角是否有冲突 横纵坐标-1
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (borad[i][j] === 'Q') {
        return false;
      }
    }
    // 判断135度角是否有冲突
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (borad[i][j] === 'Q') {
        return false;
      }
    }
    return true;
  }
  //3. 转换成字符串
  function transformborad(borad) {
    return borad.map((i) => i.join(''));
  }

  let result = [];
  function backTrack(row, borad) {
    if (row === n) {
      result.push(transformborad(borad));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col, borad, n)) {
        borad[row][col] = 'Q';
        backTrack(row + 1, borad);
        borad[row][col] = '.'; // 回溯操作
      }
    }
  }
  backTrack(0, borad);
  return result;
};

37. 解数独

N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

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
            }
        }
        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++) {
                    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

};