Combination sum

思路：此题很简单，只需用DFS每次添加一个元素即可。 
1 class Solution {
 2 public:
 3     
 4     void DFS(vector<int> candidates, int target, vector<vector<int> > &result,int k,vector<int> a){
 5         
 6         if (k == target/min(candidates.front(),candidates.back())+1) return;
 7         if (a.size() != 0){
 8             
 9             int sum = 0;
10             for (int i=0; i<a.size(); i++) sum += a[i];
11             if (sum == target) result.push_back(a);
12         }
13         
14       
15             
16         k = k+1;
17         for (int i=0;i<candidates.size();i++){
18                 
19             a.push_back(candidates[i]);
20             DFS(candidates,target,result,k,a);
21             a.pop_back();
22         }
23     }
24     
25     vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
26         // Start typing your C/C++ solution below
27         // DO NOT write int main() function
28         vector<vector<int> > result;
29         if (candidates.size() == 0) return result;
30         
31         int sum =0;
32         int k = 0;
33         vector <int> a;
34         DFS(candidates,target,result,k,a);
35         
36         map<vector<int>, int> map1;
37         if (result.size()>0){
38             for (int i = 0; i<result.size(); i++){
39                 sort(result[i].begin(),result[i].end());
40                 map1[result[i]]= i;
41                 
42             }
43             
44             result.clear();
45             map<vector<int>, int>::iterator it;
46             for (it=map1.begin(); it!=map1.end();it++)
47                 result.push_back(it->first);
48             
49             
50         }
51         return result;
52     }
53     
54 };