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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). – The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]
思路
）.
class Solution {public:vector<vector<int> > combinationSum(vector<int> &candidates, int target) {vector<vector<int> > ret;vector<int>::iterator i, cbeg = candidates.begin(), cend = candidates.end();sort(cbeg, cend);for(i = cbeg; i < cend; i++){if(*i == target){ //既是递归出口也是一种casevector<int> tmp(1, *i);ret.push_back(tmp);}else if(*i < target){vector<int> c(i, cend);//先确定一个元素*i,再进行递归，将target逐步变小vector<vector<int> > pre = combinationSum(c, target – *i);if(!pre.empty()){ //如果非空，则将*i元素添加至各个组合中for(vector<vector<int> >::iterator vec = pre.begin(); vec < pre.end(); vec++){(*vec).push_back(*i);sort((*vec).begin(), (*vec).end());}//将某一固定*i元素下，所有符合要求的组合添加至最终结果ret.insert(ret.end(), pre.begin(), pre.end());}}else break;}return ret;}};
，不是每个人都一定快乐，不是每种痛都一定要述说。
