回溯算法是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，
当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。
回溯和普通递归的联系：回溯知道路径(递归与递归直接的状态)，普通递归不关心路径(递归递归之间的关联状态)
排列问题leetcode-46: 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
function permute(nums: number[]): number[][] {
const result: number[][] = []
const selectArr = nums.map(() => false)
foo(nums, result)
return result
function foo(nums: number[], result: number[][], path: number[] = []) {
// 终止条件
if (path.length === nums.length) {
result.push([...path])
return
}
for (let i = 0; i < nums.length; i++) {
// 剪枝，防止重复元素，排除[1,1,1]
if (selectArr[i] === false) {
selectArr[i] = true
path.push(nums[i])
foo(nums, result, path)
path.pop()
selectArr[i] = false
}
}
}
}
子集(组合)问题leetcode-78: 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
function function subsets(nums: number[]): number[][] {
const result: number[][] = []
const path: number[] = []
foo(path, nums, 0)
return result
function foo(path: number[], nums: number[], start: number) {
if (path.length <= nums.length) {
result.push([...path])
}
for (let i = start; i < nums.length; i++) {
const item = nums[i]
path.push(item)
// 剪枝
// 数组中的元素 互不相同，
// 这是组合问题，直接从当前的下一个取，就保证了不重复，并且顺序也固定了，就是从左到右
foo(path, nums, i + 1) // 套路
path.pop()
}
}
}
切割问题leetcode-131: 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
function partition(s: string): string[][] {
const result: string[][] = []
const path: string[] = []
foo(s, path)
return result
function foo(s: string, path: string[]) {
if (s.length === 0) {
result.push([...path])
return
}
// 按照字符进行拆分
// 第一轮
// 比如 :a,ab
// 比如 :a,b
// 第二轮
// 比如 :aa,b
for (let i = 1; i <= s.length; i++) {
const charCode = s.slice(0, i)
// 剪枝
if (charCode.split('').reverse().join('') === charCode) {
path.push(charCode)
foo(s.slice(i), path)
path.pop()
}
}
}
}
function foo(nums: number[], result: number[][], path: number[] = []) {
// 终止条件
if (path.length === nums.length) {
result.push([...path])
return
}
for (let i = 0; i < nums.length; i++) {
// 剪枝
if (selectArr[i] === false) {
selectArr[i] = true
path.push(nums[i])
foo(nums, result, path)
path.pop()
selectArr[i] = false
}
}
}