一、问题描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
题目链接：组合
二、题目要求
样例
输入： n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
考察
1.回溯算法 2.建议用时15~25min
三、问题分析
这一题主要考察回溯算法，之前刷题很少刷到这一种类型的题目，今天我尽量讲得详细易懂一点。关注这个算法题每日一练的专栏，后续会逐渐多出一些考察回溯算法的题目。
正式讲解之前，我们先思考一下：只最简单的编程，不用任何算法如何解决？
以样例为例，1 2 3 4 选出集合个数为2的子集，用两重for循环不就解决了。
int i,j,n=4; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { cout<<i<<" "<<j<<"\n"; } }
那假如n=10,k=3，三重循环就行。n=100,k=50呢？
不可能要写50重for循环吧，骡子也撑不住这样写代码啊。
所以，我们的主角，回溯大法就要来了，此招式分为四式：
第一式：函数初始
我们要初始化一个函数来承载回溯，函数里面的参数如何确定呢？
首先，如上图所示这一题从1开始，到n结束，要求集合里面k个数字。
vector<int>t; vector<vector<int>>v;//初始化数组 void DFS(int cur,int n,int k)
第二式：终止条件
什么时候结束继续向下开始搜索的条件呢？
题目要求k个数字，所以只要
if(t.size()==k)//符合要求 { v.push_back(t); return; }
第三式：剪枝优化
但对于执行到一半，我们就知道不可能出现结果的部分可以优化，这部分称为剪枝，就是去掉多余的枝条不影响结果。
假设1 2 3 4 5里面选择3个数字，那么遍历到4为开头的时候，就发现无论如何遍历都不能满足3个数字，这个时候不需要向下遍历。
if (t.size()+(n-cur + 1) < k) return;
第四式：递归处理
for(int i=cur;i<=n;i++) { t.push_back(i);//选择当前数字 DFS(i+1,n,k); t.pop_back();//回退 }
cur代表的是当前的数字，我们要向下加入数字到集合之中，DFS下面的一行代表什么？
假如现在t里面存储了1 2，如果我们不把2弹出，那么3如何加入进来。
过程应该是：
加入后：1 加入后：[1 2] 回溯后：1 加入后：[1 3] 回溯后：1 加入后：[1 4] 回溯后：1 回溯后：[] 加入后：2 加入后：[2 3] 回溯后：2 加入后：[2 4] 回溯后：2 回溯后：[] 加入后：3 加入后：[3 4]
模板：
void DFS(变量)//函数初始 { if(条件1||条件2...)//终止条件 { v.push_back(t); return; } if (条件1||条件2...)//剪枝 return; for(int i=cur;i<=n;i++)//递归处理 { //选择当前数字 DFS(向下遍历); //回退 } }
冲冲冲！
四、编码实现
classSolution { public: vector<int>t; vector<vector<int>>v;//初始化数组voidDFS(intcur,intn,intk)//函数初始 { if(t.size()==k)//终止条件 { v.push_back(t); return; } if (t.size()+(n-cur+1) <k)//剪枝return; for(inti=cur;i<=n;i++)//递归处理 { t.push_back(i);//选择当前数字DFS(i+1,n,k); t.pop_back();//不选当前数字 } } vector<vector<int>>combine(intn, intk) { DFS(1,n,k); returnv; } };
五、测试结果
图2优化后的结果。
做完了上面一题之后，我们再用相同的套路做一个同等类型的题目。
组合总和
一、问题描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
题目链接：组合总和
二、题目要求
样例
输入： candidates = [2,3,6,7], target = 7 输出： [[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
考察
1.回溯算法 2.建议用时20~35min
三、问题分析
本题是开启回溯算法刷题的第1题，之前没有了解过可以看一下这篇题解，讲解比较详细。
一开始拿到这一题，我想到的是逐渐加上每一个数字，但这种方法远没有target逐渐减去一个值，直到为0来得巧妙。
第一式：函数初始
我们要初始化一个函数来承载回溯，函数里面的参数如何确定呢？
首先，要传入给定的数组信息，目标值，初始遍历的下标。
vector<int>t; vector<vector<int>>v; void DFS(int start,int target,vector<int>&candidates)//初始信息
第二式：终止条件
什么时候结束继续向下开始搜索的条件呢？
题目要求target可以由数组的哪些元素组成，每加入一个元素，target要减去这个元素的值。
如果target==0，那么就符合终止条件。
if(target==0)//符合要求 { v.push_back(t); return; }
第三式：剪枝优化
这一题剪枝比较简单，上面终止的条件不是等于0咩。
那如果target已经小于0，那我们还有必要继续搜索吗，完全没必要。
if(target<0)//剪枝 return;
第四式：递归处理
for(int i=start;i<candidates.size();i++)//递归处理 { if(candidates[i]<=target)//加了一个小判断 { t.push_back(candidates[i]); DFS(i,target-candidates[i],candidates); t.pop_back(); } }
上面的代码为啥这样写，我简单讲解一下。
因为题目说数组里面的数字可以重复使用，所以我们DFS里面的i是没有执行+1操作的。
像上面的执行图一样7一直执行-2操作，最后的叶子结点是-1，开始向上回退一步-3，正好符合条件，存储结果。重复上面的过程就可以了。
模板：
void DFS(变量)//函数初始 { if(条件1||条件2...)//终止条件 { v.push_back(t); return; } if (条件1||条件2...)//剪枝 return; for(int i=cur;i<=n;i++)//递归处理 { //选择当前数字 DFS(向下遍历); //回退 } }
冲冲冲！
四、编码实现
classSolution { public: vector<int>t; vector<vector<int>>v; voidDFS(intstart,inttarget,vector<int>&candidates)//函数初始 { if(target==0)//终止条件 { v.push_back(t); return; } if(target<0)//剪枝return; for(inti=start;i<candidates.size();i++)//递归处理 { if(candidates[i]<=target)//加了一个小判断 { t.push_back(candidates[i]); DFS(i,target-candidates[i],candidates); t.pop_back(); } } } vector<vector<int>>combinationSum(vector<int>&candidates, inttarget) { DFS(0,target,candidates);//导入数据returnv; } };
五、测试结果
