# [leetcode] Combination Sum

### Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set `2,3,6,7` and target `7`,
A solution set is:
`[7]`
`[2, 2, 3]`

Tags: array, backtracking

C++:

```class Solution {
public:
void _combinationSum(vector<vector<int> >& resultSet, vector<int>& currentResult, vector<int> & candidates, vector<int>::iterator start, int target){
/**resultSet: the return value, final result
* currentResult: current possible result. it's an element of final result.
* candidates: sorted candidates value
* start: start iterator of candidates. add this parameter to avoid duplicate results.
* target: current target. It decreses by recursing, increases by backtracking.
* BUG: Duplicate results.
**/
if (target == 0){
//found a solution
vector<int> re(currentResult);
sort(re.begin(), re.end());
resultSet.push_back(re);
return;
}
else{
//target > 0, continue to find a solution beneath current branch
for(vector<int>::iterator it = start; it != candidates.end(); it++){
if(*it > target){
//candidates are sorted in increasing order, if *it > target, all the following elements in candidates is bigger than target.
break;
}
else{
//push current element, go deeper
currentResult.push_back(*it);
_combinationSum(resultSet, currentResult, candidates, it, target - *it);
currentResult.pop_back();
}
}
}
}

vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector<vector<int> > resultSet;
vector<int> currentResult;

if(candidates.empty()){
return resultSet;
}

sort(candidates.begin(), candidates.end());
_combinationSum(resultSet, currentResult, candidates, candidates.begin(), target);

return resultSet;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.