前言
今日感悟：
不患寡而患不均。
一、回溯的概念
我听说绝大部分的回溯都可以转换成这张图（代码随想录）
这好像是我们以前数学学过的分组一个一个找的形式。找到一个子集合，我们就回溯，然后继续找。
二、组合
class Solution { public: vector<int> path; vector<vector<int>> res; void backtracking(int n,int k,int startindex) { if(path.size()==k) //长度达到要求就储存，然后返回 { res.push_back(path); return ; } for(int i=startindex;i<=n;i++) //第一次到是第二层，然后第二次到是遍历剩下的元素 { path.push_back(i); backtracking(n,k,i+1); //因为数字不重复，所有传进i+1 path.pop_back(); //回溯，删掉尾巴，再储存下一个 } } vector<vector<int>> combine(int n, int k) { backtracking(n,k,1); return res; } };
剪枝优化：
假设我们的n=5,k=4，也就是我们有1 2 3 4 5，五个数字，找四个数字的集合，因为我们要的结果集是4个数字，根据回溯算法特点，那么我们遍历的时候开始的位置最大就从2开始，那我们要怎么确定遍历的位置呢，我们需要的元素等于什么，等于n-（k-path.size()）+1。这样我们就能算出最大能从哪里开始，那为什么要+1，这里建议直接举例子了。
class Solution { public: vector<int> path; vector<vector<int>> res; void backtracking(int n,int k,int startindex) { if(path.size()==k) { res.push_back(path); return ; } for(int i=startindex;i<=n-(k-path.size())+1;i++) //关键点在这 { path.push_back(i); backtracking(n,k,i+1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracking(n,k,1); return res; } };
总结
回溯，模板化很强，加油！！1
