回溯

与递归相辅相成;回溯是递归的副产品，只要有递归就会有回溯。
回溯函数也就是递归函数，指的都是一个函数。

回溯搜索法

纯暴力搜索
解决的问题

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式(与组合差别，排列有元素顺序)
棋盘问题：N皇后，解数独等等

理解

抽象的不易理解；抽象为图形结构--树形结构
N叉树【树的宽度：集合的大小（for处理）；深度：递归的深度（递归处理）】

模板

void backtracking(参数){
  if(终止条件){
    收集结果；
    return；
  }

  //单层搜索
   for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小)）{//集合元素集
      处理节点；
      backtracking(路径，选择列表);//递归函数；
      回溯操作； //（12，把2回溯，变13；没有回溯操作就会递归为123）
    }
  return；
}

leetcode题目

组合

77.组合

for循环嵌套太多层了

热门相关：仙城纪   霸皇纪   情生意动   薄先生，情不由己   霸皇纪