1.理论基础

回溯和递归是相辅相成的.

• 隐藏在哪里呢?
  通常是递归函数的下面.
  二叉树的递归就是,只不过有的题目用到了回溯,有的没用到.
• 效率
  并不是高效的算法,纯暴力
• 能解决的问题:
  1. 组合问题
     组合是强调没有顺序的
     给你一个集合[1,2,3,4]问你大小为2的组合.比如[1,2];[2,3]...
  2. 切割问题
     给你一个字符串,问你有几种切割方式/如何切割才能保证子串都是回文子串
  3. 子集问题
     如集合[1,2,3,4]的全部子集
  4. 排列问题
     排列是强调有顺序的
  5. 棋盘问题
     N皇后/解数独
• 回溯法抽象成图来理解
  回溯法可以抽象成一个树形结构

  const backtracking = ()=>{
     if(终止条件){
      //收集结果
      return;
     }
     for(放集合的元素集){
     //处理节点
     //递归函数
     //回溯操作
     }
  }
  

image.png

2. 77.组合

题目
题解

如果只是单纯用for循环嵌套,少了还好说,如果要的是n=100,k=50的所有集合呢?

• 这题的startIndex不是下标,而是具体的值,所以是从1开始

• 过程:

  
  
  image.png
• 以及在leetcode上设全局变量记得要清空,不然不同case会相互影响.