Well, a typical backtracking problem. Make sure you are clear with the following three problems:
Of course, remember to recover to the previous status once a partial solution is done. In the following code, line 18 (comb.pop_back()) is for this purpose.
The following should be self-explanatory :)
1 class Solution { 2 public: 3 vector<vector<int>> combinationSum(vector<int>& candidates, int target) { 4 sort(candidates.begin(), candidates.end()); 5 vector<vector<int> > res; 6 vector<int> comb; 7 combination(candidates, 0, target, comb, res); 8 return res; 9 } 10 private: 11 void combination(vector<int>& candidates, int start, int remain, vector<int>& comb, vector<vector<int> >& res) { 12 if (!remain) { 13 res.push_back(comb); 14 return; 15 } 16 for (int i = start; i < (int)candidates.size(); i++) { 17 if (remain >= candidates[i]) { 18 comb.push_back(candidates[i]); 19 combination(candidates, i, remain - candidates[i], comb, res); 20 comb.pop_back(); 21 } 22 } 23 } 24 };
原文：http://www.cnblogs.com/jcliBlogger/p/4584712.html