# Concise Backtracking Solution

• We backtrack from successful searches as well because they are saved at the leafs of recursion tree

``````class Solution {
public:

void search(vector<int>& num, int next, vector<int>& pSol, int target, vector<vector<int> >& result)
{
if(target == 0)
{
result.push_back(pSol);
return;
}

if(next == num.size() || target - num[next] < 0)
return;

pSol.push_back(num[next]);
search(num, next, pSol, target - num[next], result);
pSol.pop_back();

search(num, next + 1, pSol, target, result);
}

vector<vector<int> > combinationSum(vector<int> &num, int target)
{
vector<vector<int> > result;
sort(num.begin(), num.end());
vector<int> pSol;
search(num, 0, pSol, target, result);
return result;
}
};``````

• This post is deleted!

• Concise solution.

But a shortcoming of this solution is, that for the same number, it still increases call stack which is not necessary. This line:

``````search(num, next, pSol, target - num[next], result);
``````

This can be replaced with a for-loop. Otherwise, for a input like candidates==[1] and target==10000, this solution will immediately have a 10000 level call stack, which might exceed OS's tolerance.

What do you think?

• what if the input is [2,2],4?

• Here is my java backtracking solution,it's easy to understand.

``````public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> sets = new ArrayList<List<Integer>>();
backTrack(sets,new ArrayList<Integer>(),candidates,0,target,candidates.length-1);
return sets;
}
public void backTrack(List<List<Integer>> sets,List<Integer> path,int[] nums,int sum,int target,int index){
if(sum==target){
return;
}
if(sum>target){
return;
}
for(int i=index;i>=0;i--){
sum += nums[i];
backTrack(sets,path,nums,sum,target,i);
sum -= nums[i];
path.remove(0);
}
}
``````

}

• I don't know how to replace this line with a for loop. Could you give me some hint? Thanks.

• similar backtracking solution

``````void elementSum(vector<int>&candidates,vector<vector<int>>&res,vector<int>&elements,int target ,int begin){
if(!target){
res.push_back(elements); return;
}
for(int i=begin;i<candidates.size() && candidates[i] <= target ;i++){
elements.push_back(candidates[i]);
elementSum(candidates,res,elements,target-candidates[i],i);
elements.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int>elements;
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());
elementSum(candidates,res,elements,target,0);
return res;
}``````

• @rakesh_joshi Hey Joshi, your code is great. I have a recursion related problem. I only see there is one "return" condition. What if there exist a situation where we can't find a vector the sum of which equals to target? Where does this code return?

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