Problem Description: http://oj.leetcode.com/problems/combination-sum/
Basic idea: It seems complicate at first. But once I got the recursive idea, the solution was neat. This code could be not efficient. I will rewrite with dynamic programming next time.
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
std::sort(candidates.begin(), candidates.end());
vector<vector<int> > combinations;
for(int i = ; i < candidates.size(); i ++) {
if(candidates[i] > target)
break;
if(candidates[i] == target) {
vector<int> combination;
combination.push_back(candidates[i]);
combinations.push_back(combination);
}else{
if(i == && target % candidates[i] != )
continue;
if(i == && target % candidates[i] == ){
vector<int> combination(target / candidates[i], candidates[i]);
combinations.push_back(combination);
continue;
}
vector<int> sub_candidates(candidates.begin(), candidates.begin() + i + );
vector<vector<int> > rests = combinationSum(sub_candidates, target - candidates[i]);
for(auto item: rests){
item.push_back(candidates[i]);
combinations.push_back(item);
}
}
}
return combinations;
}
};