题目链接：https://leetcode-cn.com/problems/combination-sum/
题目说明：
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
示例 1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
示例 4：
输入: candidates = [1], target = 1
输出: [[1]]
示例 5：
输入: candidates = [1], target = 2
输出: [[1,1]]
题目思想：
本题会涉及到一个新的算法思想：回溯算法
1、本题属于组合总和的问题，特点是，组合不排序；可以使用回溯法，也是一种树形结构
2、回溯法的三部曲 1） 确定函数的参数以及返回值类型
2）确定终止条件<递归>
3）确定单层的搜索逻辑
3、此题的函数已经给出，返回值为整型集合，参数为输入的candidates 集合和目标值target
终止条件为sum 总和 = target 则返回集合；sum 总和若 > target 则直接return（）
单层的搜索逻辑，为for 循环进行判定集合数值
题目代码：
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { //思想 ：用target 与 candidates数组元素进行一对一相减，若减值等于0，则进行输出该数组元素 //若一对一遍历结束，则进行一对2 //定义一组全局变量，二维数组，存放结果集 vector<vector<int>> ret; //定义一组全局变量，存放单一树形结果集 vector<int> now; //初始化sum的总和为0；并且获取candidates的集合长度 int sum = 0, n = candidates.size(); function<void(int)> dfs = [&] (int back) { if (sum == target) { ret.emplace_back(begin(now), end(now)); } else if (sum > target) return; else { for (int i = back; i != n; ++i) { now.push_back(candidates[i]); sum += candidates[i]; dfs(i); sum -= candidates[i]; now.pop_back(); } } }; dfs(0); return ret; } };
TIps；push_back 与 emplace_back 的区别
1、两者函数都是将数值进行插入到容器末尾，区别是push_back 是先创建元素，再将元素进行拷贝或者移除到容器；而emplace_back 是直接在容器的末尾创建元素。相比之下，节省了移除或者拷贝元素的时间。