目录回溯的目标是要返回所有符合条件的结果的集合暴力搜索回溯的遍历类似树的遍历​编辑回溯三部曲1递归函数的返回值以及参数2回溯函数终止条件3单层搜索的过程经典问题组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式 abcdef子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等回溯的目标是要返回所有符合条件的结果的集合暴力搜索回溯的遍历类似树的遍历for循环-横向遍历-集合大小树的宽度递归-纵向遍历-树的深度回溯三部曲1递归函数的返回值以及参数2回溯函数终止条件3单层搜索的过程经典模板void backtracking(参数) { if (终止条件) { 存放结果; return; } ​ for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; //处理 backtracking(路径选择列表); // 递归 回溯撤销处理结果 //还原现场 } }解题技巧返回值一般是void先写逻辑再填参数经典问题组合问题N个数里面按一定规则找出k个数的集合1写出集合数组 是[1,2,3,...,n]画出树结构2写回溯函数①终止条件长度为k时加到结果里并返回②遍历for范围是集合中元素的个数递归的索引是从当前的下一个元素开始因组合无序3组合数是无序的用过的不能再用因此for遍历起始值是当前元素的idx递归的索引是从当前的下一个元素开始*如果是多个集合取组合各个集合之间相互不影响那么就不用idx*如果元素是可重复选取的递归的i的idx不需要1*如果集合中元素有重复但只能用集合中的就需要用used标记/idx去重还要先排序sort(candidates.begin(), candidates.end()); 操作的时候加判断是否与上个数字重复4定义全局变量结果数组和中间结果数组class Solution { vectorvectorint result;// 存放符合条件结果的集合 vectorint temp;// 用来存放符合条件结果 public: void backtracking(vectorint nums, int n, int k,int idx){ if(temp.size()k){ result.push_back(temp); return; } for(int iidx;in;i){//剪枝优化 in-(k-temp.size())1 temp.push_back(nums[i]); backtracking(nums,n,k,i1); temp.pop_back(); } } vectorvectorint combine(int n, int k) { vectorint nums; for(int i0;in;i){ nums.push_back(i1); } backtracking(nums,n,k,0); return result; } };优化如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了那么就没有必要搜索了。切割问题一个字符串按一定规则有几种切割方式 abcdef-选取一个a之后在bcdef中再去选取第2个选取b之后在cdef中再选取第3个。-切割一个a之后在bcdef中再去切割第2段切割b之后在cdef中再切割第3段。// 获取[startIndex,i]在s中的子串 string str s.substr(startIndex, i - startIndex 1);子集问题一个N个数的集合里有多少符合条件的子集相当于没有终止条件的组合是统计所有节点组合是统计所有叶子节点排列问题N个数按一定规则全排列有几种排列方式每层都是从0开始搜索而不是startIndex需要used数组记录temp里都放了哪些元素了棋盘问题N皇后解数独等等