39. Combination Sum
Given a set ofcandidate numbers (C) (without duplicates) and atarget number (T), find all unique combinations in C wherethe candidate numbers sums to T.
The same repeatednumber may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.For example,given candidate set [2, 3, 6, 7] and target 7,
给定一个数组，然后再给定一个target的值，选择数组中的若干个元素的值求和，使得这个和的值等于target，然后记录下这些元素并返回。
PS：每个元素可以多次使用，并且相同的元素组合只需记录一次，如[1,2,3]和[3,2,1]等价，只需返回[1,2,3]。
如[2,1] ， target = 5
返回结果：
[1,1,1,1,1] ,[1,1,1,2] , [1,2,2] 。
可以采用深度优先遍历(dfs)，考虑优化dfs，也就是剪枝，大大加快了算法的速度。
因为查找几个元素是否满足和等于target，至少就需要二重遍历，所以复杂度是大于O(n)的，那么可以考虑先将数组排序，再进行dfs，利用vector模拟栈操作。
1． 初始化当前和记为s，当前栈为v。
2． 若s等于target，则把v中的所有元素记录，并回溯。
3． 若s不等于targe，从头开始遍历数组，更新s的值，新的s的值等于旧的s值加上当前遍历到的元素：
a) 若新的s值大于target的值，回溯，s值等于旧的s。//剪枝
b) 若新的s值小于等于target的值，就跳到2。//dfs
private : int s; vector<int> v; vector< vector<int> >result; public: void dfs(vector<int> ca,int target , int now){ // cout << "s -> " << s << " " << target<< endl; if(s == target){ result.push_back(v); // cout << "r -> "; } for(int i = now ; i < ca.size() ; i++){ if(s + ca[i] <= target){ // if <= target v.push_back(ca[i]); s += ca[i]; // cout << "ca[i] -> " << ca[i] << endl; dfs(ca,target,i); s -= v.back(); v.pop_back(); // cout << endl << " ret "<<endl; } else{ return; } }//for(i) } vector<vector<int>> combinationSum(vector<int>& ca, int target) { sort(ca.begin(),ca.end()); for(int i = 0; i < ca.size() ; i++){ s = 0; s += ca[i]; v.push_back(ca[i]); dfs(ca,target,i); v.pop_back(); }//for(i) return result; }