回溯算法
回溯算法是算法设计中的一种方法，算法的一种设计思想。是一种渐进式寻找并构建问题解决方式的策略。回溯算法会从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决。
什么问题适合用回溯算法解决：
有很多路。
这些路里，有死路，也有出路。
通常需要递归来模拟所有的路。
例如：全排列问题：
用递归模拟出所有情况。
遇到包含重复元素的情况，就回溯（不要在遍历）。
收集所有到达递归终点的情况，并返回。
举例算法题一：全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]解题思路：
前提要求：1、所有排列情况；2、没有重复元素
- 有出路，有死路
- 考虑使用回溯算法
解题步骤：
1、用递归模拟出所有情况。
2、遇到包含重复元素的情况，就回溯（不在递归下去）。
3、收集所有到达终点的情况，并返回。
解题答案：
var permute = function(nums){
const res = []; //所有出路
const backrack = (path) =>{ //递归
//收集满足要求的排列组合,递归的终点
if(path.length === nums.length){
res.push(path);
return;
}
nums.forEach(n => {
if(path.includes(n)){ return;} //一些路是死路,就回溯
backrack(path.concat(n)); //下一次递归加到数组里面
});
}
backrack([]); //[1,2,3]
return res;
}
var arr = [1,2,3,4]
console.log(permute(arr))算法分析：
时间复杂度最复杂的，嵌套的for循环，是 O(n!),n!= 1*2*3#…(n-1)*n;
空间复杂度是，输出的数组用到递归（堆栈），递归的深度N：O(n)。
举例算法题二：子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2：
输入：nums = [0]
输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
解题思路：
要求：1、所有的子集；2、没有重复元素和子集
有出路，有死路
考虑使用回溯算法
解题步骤：
1、用递归模拟出所有情况。写递归函数遍历每一个数。
2、保证接的数字都是后面的数字。
3、收集所有到达递归终点的情况，并返回。
解题答案：
var subsets = function(nums){
const res = []; //用来最为最终输出的大数组
const backtrack = (path, l, start) =>{ //backtrack回溯的意思,参数是路径、长度、下标
if(path.length === l){ //收集到终点的情况
res.push(path);
return;
}
for(let i = start; i <= nums.length; i += 1){
backtrack(path.concat(nums[i]), l, i + 1);
}
}
for(let i = 0; i <= nums.length; i += 1){
backtrack([],i,0) //参数是路径、长度、下标
}
return res;
}
var arr = [1,2,3]
console.log(subsets(arr))算法分析：
时间复杂度:O(2^N),因为每个元素都有可能有两种可能（存在或不存在）；
空间复杂度是O(N) 递归堆栈放的临时变量。
