回溯理论基础及leetcode

回溯

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

回溯搜索法

纯暴力搜索
解决的问题

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

理解

抽象的不易理解;抽象为图形结构--树形结构
N叉树【树的宽度:集合的大小(for处理);深度:递归的深度(递归处理)】

模板

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

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

leetcode题目

组合

77.组合

for循环嵌套太多层了

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