题目描述:
Given a set of candidate numbers ( C ) and a target number ( T ),
find all unique combinations in C where the candidate numbers sums to T .
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
//非降序
Elements in a combination (a 1, a 2, … , a k) must be in non-descending order.
(ie, a 1 ≤ a 2 ≤ … ≤ a k).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7and target 7,
A solution set is:
[7]
[2, 2, 3]
思路：
前缀+一个元素，一层一层的产生，同一前缀加一个不同的元素，不同前缀之间由于前缀不同自然加一个元素产生的一定不同，其实本质还是枚举一个前缀下一个位置的能取值的所有情况。
代码：
1 class Solution {
2 public:
3 vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
4
5 vector<vector<int>> ret;
6 sort(candidates.begin(),candidates.end());
7 vector<int> temp;
8 int curSum = 0;
9 combinationSumCore(candidates,0,ret,temp,curSum,target);
10 return ret;
11 }
12
13
14 void combinationSumCore(vector<int> &candidates,int start,vector<vector<int>> &ret,vector<int> &temp,int &curSum,int target)
15 {
16 //主要是由于这里递归时传入的start为i(不是i+1),而i的范围天然的在[start,candidates.size()),一定不会越界
17 // if(start == candidates.size())
18 // return;
19 for(int i = start;i < candidates.size();i++)
20 {
21
22 curSum += candidates[i];
23 if(curSum > target)
24 {
25 curSum-=candidates[i];
26 return;//剪枝
27 }
28 else if(curSum == target)
29 {
30 temp.push_back(candidates[i]);
31 ret.push_back(temp);
32 temp.pop_back();
33 curSum-=candidates[i];
34 return;//剪枝
35 }
36 else
37 {
38 temp.push_back(candidates[i]);
39 combinationSumCore(candidates,i,ret,temp,curSum,target);
40 temp.pop_back();
41 curSum-=candidates[i];
42 }
43
44 }
45
46 }
47
48
49 };
原文：https://www.cnblogs.com/zjuhaohaoxuexi/p/11784664.html