一、回溯算法
1.1什么是回溯？
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。——摘自《百度百科》
1.1 一般步骤：
- 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
- 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
- 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
1.2 如何理解回溯算法？
- 为问题建立解空间结构
- 在解空间结构上进行DFS搜索
- 设立回溯出口和剪枝点，减少无效搜索，出口处保存有效解.
1.3 解决那些问题？
- 组合问题：N个数⾥⾯按⼀定规则找出k个数的集合
- 切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
- ⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
- 排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式
- 棋盘问题：N皇后，解数独等等。
1.4递归与回溯
首先先说明一下对递归 (Recursive)与回溯 (Backtrack)的理解。
1.4.1 递归 (Recursive)
程序调用自身的编程技巧称为递归。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 ——摘自《百度百科》
通常来说，为了描述问题的某一状态，必须用到该状态的上一个状态；而如果要描述上一个状态，又必须用到上一个状态的上一个状态…… 这样用自己来定义自己的方法就是递归。
1.4.2. 回溯 (Backtrack)
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 ——摘自《百度百科》
在这种思想下，我们需要清晰的找出三个要素：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。
1.5.递归与回溯的区别
递归是一种算法结构。递归会出现在子程序中，形式上表现为直接或间接的自己调用自己。典型的例子是阶乘，计算规律为：n!=n×(n−1)!n!=n \times (n-1)!，基本如下所示：
let fac = (n)=> { if(n == 1){ return n; }else{ return (n*fac(n - 1)); } }
回溯是一种算法思想，它是用递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。
二、Leetcode回溯题目
2.1- 22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
思路分析
- 判断左右括号所剩的数量，最初始都是n;当左括号（(）有剩余，继续做选择；
- 判断当右括号比左括号剩的多，才能选右括号；继续递归做选择
- 出口:构建的字符串是 2n的时候，此时已经该分支已经构建完成，加入选项；
简答绘制图形
解题代码
var generateParenthesis = function (n) { const res = []; const backTracing = (lRemain, rRemain, str) => { // 左右括号所剩的数量，str是当前构建的字符串 if (str.length == 2 * n) { // 字符串构建完成 res.push(str); // 加入解集 return; // 结束当前递归分支 } if (lRemain > 0) { // 只要左括号有剩，就可以选它，然后继续做选择（递归） backTracing(lRemain - 1, rRemain, str + "("); } if (lRemain < rRemain) { // 右括号比左括号剩的多，才能选右括号 backTracing(lRemain, rRemain - 1, str + ")"); // 然后继续做选择（递归） } }; backTracing(n, n, ""); // 递归的入口，剩余数量都是n，初始字符串是空串 return res; };
2.2 - 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 中的所有整数 互不相同
解题思路
- 回溯终止条件：该条路径长度与达到nums长度；
- 加入当前值到路径，如果结果里面已经包含这个路径，则不加入结果里面，否则继续选择这个选项；
解题代码
/** * @param {number[]} nums * @return {number[][]} */ var permute = function (nums) { if (!nums.length) return let res = [] let backTrack = path => { //长度满足条件，加入结果 if (path.length === nums.length) { res.push(path) return } nums.forEach(item => { if (path.includes(item)) return //不包含重复的数字 backTrack([...path, item]) //加入路径，继续递归选择 }); } backTrack([]) return res };
2.3 - n 皇后问题
研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。*
皇后走法规则
皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。
示例
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 9
解题思路
- 定义判断当前位置的检验函数，约束条件包含 ，不能同行，不能同列，不能同对角线（45度和135度）
- 定义棋盘；标准回溯处理；
使用回溯的具体做法是：依次在每一行放置一个皇后，每次新放置的皇后都不能和已经放置的皇后之间有攻击，即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上。当 NNN 个皇后都放置完毕，则找到一个可能的解，将可能的解的数量加 111。
