回溯算法其实就是我们常说的 DFS 算法，本质上就是一种暴力穷举算法。

站在回溯树的一个节点上，你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

回溯算法框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

排列：一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。

全排列-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]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var permute = function(nums) {
  const res = []
  const track = []
  const used = []
  backtrack(nums, track, used)
  return res
  function backtrack(nums, track, used) {
    if (track.length === nums.length) {
      res.push([...track])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) {
        continue
      }
      track.push(nums[i])
      used[i] = true
      backtrack(nums, track, used)
      track.pop()
      used[i] = false
    }
  }
}

function permute(nums) {
  const len = nums.length, curr = [], res = [], used = {};
  function dfs(nth) {
    if (nth === len) return res.push(curr.slice())
    nums.forEach(item => {
      if (!used[item]) {
        used[item] = true
        curr.push(item)
        dfs(nth + 1)
        curr.pop()
        used[item] = false
      }
    })
  }
  dfs(0)
  return res
}

电话号码的字母组合-17

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

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





示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]


提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var letterCombinations = function (digits) {
  const mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
  const res = [];
  if (!digits) return res;
  backtrack(digits, 0, '')
  return res;

  function backtrack(digits, index, str) {
    if (index == digits.length) {
      res.push(str);
      return;
    }

    const c = digits.charAt(index);
    const letters = mapping[c - '0'];
    for (let i = 0; i < letters.length ; i++) {
      backtrack(digits, index + 1, str + letters.charAt(i));
    }
  }
};

N 皇后-51

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

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

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

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var solveNQueens = function(n, k) {
  const res = []
  const board = []
  for (let i = 0; i < n; i++) {
    board[i] = new Array(n).fill('.')
  }
  backtrack(board, 0)
  return res

  function backtrack(board, row) {
    // 触发结束条件
    if (row === board.length) {
      const __board = board.slice()
      for (let i = 0; i < n; i++) {
        __board[i] = __board[i].join('')
      }
      res.push(__board)
      return
    }

    const len = board[row].length
    for (let col = 0; col < len; col++) {
      // 排除不合法选择
      if (!isValid(board, row, col)) {
        continue
      }
      // 做选择
      board[row][col] = 'Q'
      // 进入下一行决策
      backtrack(board, row + 1)
      // 撤销选择
      board[row][col] = '.'
    }
  }

  function isValid(board, row, col) {
    const n = board.length
    // 检查列是否有皇后互相冲突
    for (let i = 0; i <= row; i++) {
      if (board[i][col] === 'Q') { return false }
    }
    // 检查右上方是否有皇后互相冲突
    for (let i = row - 1, j = col + 1;
      i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') { return false }
    }
    // 检查左上方是否有皇后互相冲突
    for (let i = row - 1, j = col - 1;
      i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') { return false }
    }
    return true
  }
}

划分为k个相等的子集-698

给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false

提示：

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var canPartitionKSubsets = function(nums, k) {
  // 如果 k 大于数组的长度那数组肯定没法分成 k 份，直接返回 false
  if (k > nums.length) return false;
  // 记录数组中元素的和
  let sum = 0;
  for (let v of nums) sum += v;
  // 如果数组中元素的和除以 k 无法除尽，则表明无法分成 k 份
  if (sum % k != 0) return false;

  // k 个桶（集合），记录每个桶装的数字之和
  const bucket = new Array(k).fill(0);
  // 理论上每个桶（集合）中数字的和
  const target = sum / k;
  // 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
  nums.sort((a, b) => (b - a))
  return backtrack(nums, 0, bucket, target);
};

// 递归穷举 nums 中的每个数字
function backtrack(nums = [], index, bucket = [], target) {
  if (index == nums.length) {
    // 检查所有桶的数字之和是否都是 target
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i] != target) {
        return false;
      }
    }
    // nums 成功平分成 k 个子集
    return true;
  }

  // 穷举 nums[index] 可能装入的桶
  for (let i = 0; i < bucket.length; i++) {
    // 剪枝，桶装装满了
    if (bucket[i] + nums[index] > target) {
      continue;
    }
    // 将 nums[index] 装入 bucket[i]
    bucket[i] += nums[index];
    // 递归穷举下一个数字的选择
    if (backtrack(nums, index + 1, bucket, target)) {
      return true;
    }
    // 撤销选择
    bucket[i] -= nums[index];
  }

  // nums[index] 装入哪个桶都不行
  return false;
}

const nums = [4, 3, 2, 3, 5, 2, 1]
const k = 4
console.log(canPartitionKSubsets(nums, k))