思路：此题很简单，只需用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 };
转载于:https://www.cnblogs.com/tanghulu321/archive/2013/04/12/3017439.html
相关资源：数据结构—成绩单生成器
