回溯

回溯

就是暴力法都搜不出来的的递归算法

涉及到的问题

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

基本模板

for循环横向遍历，递归纵向遍历，回溯不断调整结果集

function **(){
  const cur = []
  const res = []
  backtrack(路径)
  function backtrack(路径){
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        dfs(路径); // 递归
        回溯，撤销处理结果
    }
  }
    return res
}

优化

优化回溯算法只有剪枝一种方法

总结

1. 什么时候backtrack需要索引index?

对于组合问题
- 集合来求组合的话，就需要startIndex，例如：[回溯算法：求组合问题！]
- 多个集合取组合，各个集合之间相互不影响，那么就不用startIndex 例如：[回溯算法：电话号码的字母组合]

2. 纵向去重

使用过的地方不能重复切割所以递归函数需要传入i + 1。

 backtrack(i + 1);

3. 横向去重

对于可以排序的

先排序

function backtrack(index) {
    if (sum > target) return;
    if (sum === target) return res.push(cur.slice());
    for (let i = index; i < candidates.length; i++) {
      // 横向去重，不会涉及纵向的重复元素
      if (i > index && candidates[i] === candidates[i - 1]) {
        continue;
      }
      const element = candidates[i];
      cur.push(element);
      sum += element;
      backtrack(i + 1);
      sum -= element;
      cur.pop();
    }
  }

对于可排序但是不能通过index过滤纵向的

如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

var permuteUnique = function (nums) {
  const cur = [];
  const res = [];
  const set = [];
  nums.sort((a, b) => a - b);
  backtrack();
  function backtrack() {
    if (nums.length === cur.length) {
      return res.push(cur.slice());
    }
    for (let i = 0; i < nums.length; i++) {
      if (set[i]) {
        continue;
      }
      // 去重的关键代码 !set[i - 1]
      if (i > 0 && nums[i] === nums[i - 1] && !set[i - 1]) {
        continue;
      }
      set[i] = true;
      cur.push(nums[i]);
      backtrack();
      set[i] = false;
      cur.pop();
    }
  }
  return res;
};

对于不可以排序的

// 每一次调用dfs函数 新建一个new Set()  
function dfs(index) {
    const set = new Set();
    if (current.length >= 2) {
      res.push(current.slice());
    }
    for (let i = index; i < nums.length; i++) {
      const element = nums[i];
      // 横向去重
      if (set.has(element)) {
        continue;
      }
      set.add(element);
      if (current.length && current[current.length - 1] > element) {
        continue;
      }
      current.push(element);
      dfs(i + 1);
      current.pop();
    }
  }

4. 切割问题，如何切

类似于组合问题,组合问题种，待推入的当前元素，切割问题待推入的是根据起始点，和终止点定位的一段区间

// 分割问题
const sub = s.substring(index, i + 1);
cur.push(sub);
backtrack(i + 1);
cur.pop();

// 组合问题
const sub = s[i]
cur.push(sub);
backtrack(i + 1);
cur.pop();

5. 如果涉及到数组集合有重复

就先排序

nums.sort((a, b) => a - b);

6. 排列问题是有序的，所有不用index

在排列问题种 [1,2] 和 [2,1]是不同的，需要一个哈希表存储用过的数据

// 建立哈希表
const set = new Set();
backtrack(0);
function backtrack(index) {
    if (cur.length === nums.length) {
      return res.push(cur.slice());
    }
    for (var i = 0; i < nums.length; i++) {
      if (!set.has(nums[i])) {
        // 存储当前用到的数据
        set.add(nums[i]);
        cur.push(nums[i]);
        backtrack();
        // 释放
        set.delete(nums[i]);
        cur.pop();
      }
    }
  }

组合问题

时间复杂度：O(n * 2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
空间复杂度：O(n)，和子集问题同理。

[77] 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

var combine = function (n, k) {
  const cur = [];
  const res = [];
  backtrack(1);
  function backtrack(index) {
    if (cur.length === k) {
      res.push(cur.slice());
      return res;
    }
    for (let i = index; i <= n; i++) {
      cur.push(i);
      backtrack(i + 1);
      cur.pop();
    }
  }
  return res;
};

剪枝优化

var combine = function (n, k) {
  const cur = [];
  const res = [];
  backtrack(1);
  function backtrack(index) {
    if (cur.length === k) {
      res.push(cur.slice());
      return res;
    }
    for (let i = index; i <= n - (k - cur.length) + 1; i++) {
      cur.push(i);
      backtrack(i + 1);
      cur.pop();
    }
  }
  return res;
};

[216] 组合总和 III

找出所有相加之和为 n 的 k*。*组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

var combinationSum3 = function (k, n) {
  const res = [];
  const cur = [];
  let sum = 0;
  backtrack(1);
  function backtrack(index) {
    if (sum > n) {
      return;
    }
    if (sum === n && cur.length === k) {
      res.push(cur.slice());
      return res;
    }
    for (let i = index; i <= 9 - (k - cur.length) + 1; i++) {
      cur.push(i);
      sum += i;
      backtrack(i + 1);
      sum -= i;
      cur.pop();
    }
  }
  return res;
};

[39] 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

示例 4：

输入: candidates = [1], target = 1
输出: [[1]]

示例 5：

输入: candidates = [1], target = 2
输出: [[1,1]]

var combinationSum = function (candidates, target) {
  const cur = [];
  const res = [];
  let sum = 0;
  backtrack(0);
  function backtrack(index) {
    if (sum > target) {
      return;
    }
    if (sum === target) {
      res.push(cur.slice());
      return;
    }
    for (let i = index; i < candidates.length; i++) {
      const element = candidates[i];
      if (sum + element > target) {
        continue;
      }
      sum += element;
      cur.push(element);
      backtrack(i);
      sum -= element;
      cur.pop();
    }
  }
  return res;
};

[17] 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

var letterCombinations = function (digits) {
  const map = [
    '',
    '',
    'abc',
    'def',
    'ghi',
    'jkl',
    'mno',
    'pqrs',
    'tuv',
    'wxyz',
  ];
  const cur = [];
  const res = [];
  if (!digits) return [];
  if (digits.length === 1) return map[digits].split('');
  backtrack(0);
  function backtrack(index) {
    if (cur.length === digits.length) {
      res.push(cur.slice().join(''));
      return res;
    }
    for (const item of map[digits[index]]) {
      cur.push(item);
      backtrack(index + 1);
      cur.pop();
    }
  }
  return res;
};

[40] 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

var combinationSum2 = function (candidates, target) {
  candidates.sort((a, b) => a - b);
  const res = [];
  const cur = [];
  let sum = 0;
  backtrack(0);
  function backtrack(index) {
    if (sum > target) return;
    if (sum === target) return res.push(cur.slice());
    for (let i = index; i < candidates.length; i++) {
      if (i > index && candidates[i] === candidates[i - 1]) {
        continue;
      }
      const element = candidates[i];
      cur.push(element);
      sum += element;
      backtrack(i + 1);
      sum -= element;
      cur.pop();
    }
  }
  return res;
};

切割问题

[131].分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

var partition = function (s) {
  const res = [];
  const cur = [];
  backtrack(0);
  function backtrack(index) {
    if (index >= s.length) {
      res.push(cur.slice());
      return;
    }
    for (let i = index; i < s.length; i++) {
      if (isPalindrome(s, index, i)) {
        const sub = s.substring(index, i + 1);
        console.log(sub);
        cur.push(sub);
        backtrack(i + 1);
        cur.pop();
      }
    }
  }
  function isPalindrome(s, l, r) {
    for (let i = l, j = r; i < j; i++, j--) {
      if (s[i] !== s[j]) {
        return false;
      }
    }
    return true;
  }
  return res;
};

[93] 复原 IP 地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

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

例如：”0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

var restoreIpAddresses = function (s) {
  const res = [];
  const cur = [];
  backtrack(0);
  function backtrack(index) {
    if (cur.length > 4) {
      return;
    }
    if (cur.length === 4 && index === s.length) {
      res.push(cur.slice().join('.'));
      return;
    }
    for (let i = index; i < s.length; i++) {
      const str = s.substring(index, i + 1);
      if (str.length > 3 || +str > 255) break;
      if (str.length > 1 && str[0] === '0') break;
      cur.push(str);
      backtrack(i + 1);
      cur.pop();
    }
  }
  return res;
};

子集问题

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树

时间复杂度：O(n 2n)，构造每一组子集都需要填进数组，又有需要O(n)，最终时间复杂度：O(n 2^n)
空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)

[78] 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

var subsets = function (nums) {
  const res = [];
  const cur = [];
  backtrack(0);
  function backtrack(index) {
    res.push(cur.slice());
    for (let i = index; i < nums.length; i++) {
      const element = nums[i];
      cur.push(element);
      backtrack(i + 1);
      cur.pop();
    }
  }
  return res;
};

[90] 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

var subsetsWithDup = function (nums) {
  const res = [];
  const cur = [];
  nums.sort((a, b) => a - b);
  backtrack(0);
  function backtrack(index) {
    res.push(cur.slice());
    for (var i = index; i < nums.length; i++) {
      if (i > index && nums[i - 1] === nums[i]) {
        continue;
      }
      cur.push(nums[i]);
      backtrack(i + 1);
      cur.pop();
    }
  }
  return res;
};

[491] 递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是 2 。

示例：

输入：[4, 6, 7, 7]
输出：[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

提示：

给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

var findSubsequences = function (nums) {
  const res = [];
  const current = [];
  dfs(0);

  function dfs(index) {
    const set = new Set();
    if (current.length >= 2) {
      res.push(current.slice());
    }
    for (let i = index; i < nums.length; i++) {
      const element = nums[i];
      if (set.has(element)) {
        continue;
      }
      set.add(element);
      if (current.length && current[current.length - 1] > element) {
        continue;
      }
      current.push(element);
      dfs(i + 1);
      current.pop();
    }
  }
  return res;
};

排列问题

时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n n-1 n-2 * ….. 1 = n!。
空间复杂度：O(n)，和子集问题同理。

[46] 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

var permute = function (nums) {
  const cur = [];
  const res = [];
  const set = new Set();
  backtrack(0);
  function backtrack(index) {
    if (cur.length === nums.length) {
      return res.push(cur.slice());
    }
    for (var i = 0; i < nums.length; i++) {
      if (!set.has(nums[i])) {
        set.add(nums[i]);
        cur.push(nums[i]);
        backtrack();
        set.delete(nums[i]);
        cur.pop();
      }
    }
  }
  return res;
};

[47] 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

var permuteUnique = function (nums) {
  const cur = [];
  const res = [];
  nums.sort((a, b) => a - b);
  let map = [];
  backtrack();

  function backtrack() {
    if (cur.length === nums.length) {
      return res.push(cur.slice());
    }
    for (let i = 0; i < nums.length; i++) {
      const curElement = nums[i];
      if (map[i]) {
        continue;
      }
      if (i > 0 && nums[i] === nums[i - 1] && !map[i - 1]) {
        continue;
      }
      map[i] = true;
      cur.push(curElement);
      backtrack();
      map[i] = false;
      cur.pop();
    }
  }
  return res;
};

棋盘问题

重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

var findItinerary = function (tickets) {
  const result = ['JFK'];
  const map = {};
  for (const [from, to] of tickets) {
    if (!map[from]) {
      map[from] = [];
    }
    map[from].push(to);
  }
  Object.keys(map).forEach((from) => {
    map[from].sort();
  });
  backtrack();
  function backtrack() {
    if (result.length === tickets.length + 1) {
      return true;
    }
    if (
      !map[result[result.length - 1]] ||
      !map[result[result.length - 1]].length
    ) {
      return false;
    }
    for (let i = 0; i < map[result[result.length - 1]].length; i++) {
      let city = map[result[result.length - 1]][i];
      // 删除已走过航线，防止死循环
      map[result[result.length - 1]].splice(i, 1);
      result.push(city);
      if (backtrack()) {
        return true;
      }
      result.pop();
      map[result[result.length - 1]].splice(i, 0, city);
    }
  }
  return result;
};

[51] N 皇后

Tagsbacktracking

CompaniesUnknown

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

var solveNQueens = function (n) {
  function isValid(row, col, chessBoard, n) {
    // 检查列
    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;
  }
  function transformChessBoard(chessBoard) {
    return chessBoard.map((item) => item.join(''));
  }
  const cur = new Array(n).fill([]).map(() => new Array(n).fill('.'));
  const res = [];
  dfs(0);
  function dfs(row) {
    if (row == n) {
      res.push(transformChessBoard(cur));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col, cur, n)) {
        cur[row][col] = 'Q';
        dfs(row + 1);
        cur[row][col] = '.';
      }
    }
  }
  return res;
};