LeetCode--Combination Sum

题目链接：

https://oj.leetcode.com/problems/combination-sum/

思路：

题目要求合并的答案需要升序排序。所以先排序，然后每次选一个，递归处理。

注意：每个元素可以多次，然后不能有重复的答案，所以碰到处理过的元素就不处理了。

 1 class Solution {
 2 public:
 3     vector<vector<int> >ans;
 4     vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
 5         if(candidates.size() == 0)
 6             return ans;
 7         sort(candidates.begin(),candidates.end());
 8         deque<int> res;
 9         calSum(candidates,target,0,res);
10         return ans;
11     }
12     void calSum(vector<int> &candidates,int target,int s,deque<int> &res)
13     {
14         if(target < 0)
15             return;
16         if(target == 0)
17         {
18             vector<int> restmp(res.begin(),res.end());
19             ans.push_back(restmp);
20             return;
21         }
22         int i;
23         for(i = s ; i < candidates.size() ; ++i)
24         {
25             if(i > 0 && (candidates[i] == candidates[i-1]) )
26                 continue;
27             res.push_back(candidates[i]);
28             calSum(candidates,target-candidates[i],i,res);
29             res.pop_back();
30         }
31         return;
32     }
33 };