Accepted 16ms c++ solution use backtracking, easy understand.

• Accepted 16ms c++ solution use backtracking for Combination Sum:

``````class Solution {
public:
std::vector<std::vector<int> > combinationSum(std::vector<int> &candidates, int target) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::vector<int> > res;
std::vector<int> combination;
combinationSum(candidates, target, res, combination, 0);
return res;
}
private:
void combinationSum(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) {
if (!target) {
res.push_back(combination);
return;
}
for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) {
combination.push_back(candidates[i]);
combinationSum(candidates, target - candidates[i], res, combination, i);
combination.pop_back();
}
}
};
``````

Accepted 12ms c++ solution use backtracking for Combination Sum II:

``````class Solution {
public:
std::vector<std::vector<int> > combinationSum2(std::vector<int> &candidates, int target) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::vector<int> > res;
std::vector<int> combination;
combinationSum2(candidates, target, res, combination, 0);
return res;
}
private:
void combinationSum2(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) {
if (!target) {
res.push_back(combination);
return;
}
for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i)
if (i == begin || candidates[i] != candidates[i - 1]) {
combination.push_back(candidates[i]);
combinationSum2(candidates, target - candidates[i], res, combination, i + 1);
combination.pop_back();
}
}
};
``````

Accepted 0ms c++ solution use backtracking for Combination Sum III:

``````class Solution {
public:
std::vector<std::vector<int> > combinationSum3(int k, int n) {
std::vector<std::vector<int> > res;
std::vector<int> combination;
combinationSum3(n, res, combination, 1, k);
return res;
}
private:
void combinationSum3(int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin, int need) {
if (!target) {
res.push_back(combination);
return;
}
else if (!need)
return;
for (int i = begin; i != 10 && target >= i * need + need * (need - 1) / 2; ++i) {
combination.push_back(i);
combinationSum3(target - i, res, combination, i + 1, need - 1);
combination.pop_back();
}
}
};
``````

• There is a litter problem in your code for Combination Sum.if the input is [2,2],target is 4.your
code's result is [2,2],[2,2] ,[2,2].This contain duplicate combinations.

• `[2,2]` is not a valid input for candidates because 2 is a duplicate. Please see the problem description again carefully: Given a `set` of candidate numbers (C)

• What does "i * need + need * (need - 1) / 2" means?

• target >= i + (i+1) + ... + (i +need-1) = i * need + need * (need - 1) / 2;

You can also written as follows:

``````int end = (target - need * (need - 1) / 2) / need;
if (end > 9 - need + 1)
return;
for (int i = begin; i <= end; ++i) {
combination.push_back(i);
combinationSum3(target - i, res, combination, i + 1, need - 1);
combination.pop_back();
}``````

• Combination Sum III

``````class Solution {
public:
void combination(int k, int n, vector<int>& v, vector<vector<int>>& ret, int beg){
if(k == 0 && n == 0){
ret.push_back(v);
return;
}
for(int i = beg; i < 10 && i <= n; i++){
v.push_back(i);
combination(k - 1, n - i, v, ret, i + 1);
v.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ret;
vector<int> v;
combination(k, n, v, ret, 1);
return ret;
}
};``````

• I see. You are right! I have posted my code below.

• Hi
Can someone tell me complexity of the solution ?

• What's the complexity?

• Combination Sum III:

``````void helper(int k, int target, vector<vector<int>>&r, vector<int>&temp, int pos) {
if (target == 0 && temp.size() == k)
{
r.push_back(temp);
return;
}
for (int i = pos; i <= 9; i++)
{
if (target >= i)
{
temp.push_back(i);
helper(k, target - i, r, temp, i + 1);
temp.pop_back();
}
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>>r;
vector<int>temp;
helper(k, n, r, temp, 1);
return r;
}``````

• I am trying to figure it out as well. Please let us know if anyone came up with an idea.

• Is time complexity O(n^2) ?

• First of all, thanks a lot for the answer.

My questions is that, reading a few of the top rated solution with dfs/backtracking approach, I'm wonder why no one yet exploited the fact that some of the 'subtrack' would have been 'visited' already.

e.g. if target=4, candidates=[1,2] - the ‘subtrack’ below (target-candidates[i]=2) would have been ‘visited’ more than once hence can be ‘reused’ using caching. (A bit trickier than that, we need to use only the part of the ’subtrack’ where subtrack[0] >= candidates[i] to avoid duplicate)

• Weird. The problem states:

• The solution set must not contain duplicate combinations.

Your code for Combination Sum doesn't handle the case with duplicates, but surprisingly it gets accepted by the judge.

I tried input 2,2,3,6,7and it returned [[2,2,3],[2,2,3],[2,2,3],[7]] which is what the OJ expects, but that's wrong based on the description, the correct answer should be [[2,2,3],[7]]

Am I missing something?

UPDATE: Sorry just re-read the description and the input is set, so ignore this comment.

• This post is deleted!

• There will be no this kind of problem by "&& target >= candidates[i]" in loop statement.

• I have a question, In "combination sum", why should we pop_back? I don't understand for a long time.Can anyone explain it?

• @cheffyu that's so called backtracking.

• I think your third solution is not easy to grasp and remember. Here is better version I think

``````class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> out;
help(k, n, 1, out, result);
return result;
}

void help(int k, int n, int level, vector<int>& out, vector<vector<int>>& result) {
if (n < 0) return;
if (n == 0 && k == out.size()) result.push_back(out);
for (int i = level; i <= 9; i++) {
out.push_back(i);
help(k, n - i, i + 1, out, result);
out.pop_back();
}
}
};``````

• What does combination.pop_back() do exactly? Can someone please explain this to me.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.