回溯算法

思路：

解决一个回溯问题，实际上就是一个决策树的遍历过程
画出回溯树

1. 路径：也就是已经做出的选择。
2. 选择列表：也就是你当前可以做的选择。
3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

   模板：

   const result = []
   function backtrack(路径, 选择列表){
    if (满足结束条件){
        result.push(路径)
        return
    }
    for 选择 in 选择列表{
        if(已存在/不合法)continue;
        做选择
        backtrack(路径, 选择列表)
        撤销选择
    }
   }

   其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
   
   1.全排列问题
   
   

   回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高

问题：

1. 和dfs有点像？

典型题目

1.全排列：1 2 3 4的排列组合

2.N皇后

3.子集：输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集

• 数学归纳思想

• 回溯算法 ```javascript function subsets(nums){ let result = []; let track = [];

  function backtrack(nums,start,track){

    result.push(track);

  for(let i=0;i<nums.length;i++){

    track.push(nums[i])
  backtrack(nums,i+1,track);
  track.pop()
  

  } }

  backtrack(nums,0,track);
  return result; }

<a name="OxiOO"></a>
#### 4.组合：输入两个数字 `n, k`，算法输出 `[1..n]` 中 k 个数字的所有组合
```javascript
function combine(n,k){
    const result = [];
  if(k<=0||n>=0)return results;
  const track = [];

  function backtrack(n,k,start,track){
      if(k===track.length){
      result.push(track);
        return 
    }
    for(let i=start;i<=n;i++){
        track.push(i);
      backtrack(n,k,i+1,track)
      track.pop()
    }
  }

  backtrack(n,k,1,track);
  return result;
}

5.排列：不包含重复数字的数组 nums，返回这些数字的全部排列

function permute(nums){
    let results = [],track = [];


  function backtrack(nums,track){
    if(track.length===nums.length){
        results.push(track);
      return;
    }
    for(let i=0;i<nums.length;i++){
        if(track.find(t=>t===nums[i])) continue;
      track.add(nums[i])
      backtrack(nums,track);
      track.pop()
    }
  }

  backtrack(nums,track)
  return results;
}

6.解数独

7.括号生成

• 合法括号的生成。对于括号合法性的判断，主要是借助「栈」这种数据结构，

• 括号的生成，一般都要利用回溯递归的思想

  function generateParenthesis(n){
    let res = [],track='';
  
  function backtrack(left,rigth,track){
      if(left<0 || right<0) return;//没有括号了
    //1、一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。
    //2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。
    if(left>right)return;
    if(left===0&&right===0){
        res.push(track);
      return;
    }
  
    track.push('(');
    backtrack(left-1,right,track);
    track.pop();
  
    track.push(')');
    backtrack(left,right-1,track);
    track.pop();
  }
  
  backtrack(n,n,track)
  return res;
  }