LeetCode/combinationSum.cpp at master · liuwh08/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "combinationSum.h"
#include <algorithm>

using namespace std;

void generateCombinations(vector<vector<int> >& res, vector<int>& sol, int start, int sum,const int target,const vector<int>& candidates)  {
	if(sum>target)
		return;
	if(sum == target){
		res.push_back(sol);
		return;
	}
	for (int i = start; i < candidates.size(); ++i)
	{
		if((i>0)&&(candidates.at(i) == candidates.at(i-1)))
			continue;
		sol.push_back(candidates.at(i));
		generateCombinations(res, sol, i, sum + candidates.at(i), target, candidates);
		sol.pop_back();
	}
	return;
}

vector<vector<int> > Solution::combinationSum(vector<int>& candidates, int target) {
	vector<vector<int> > res;
	vector<int> sol;
	sort(candidates.begin(), candidates.end());
	generateCombinations(res, sol, 0, 0, target, candidates);
	return res;
}