# [Help] Simple recursive backtracking solution gives TLE.

• ``````class Solution {
public:
int sum(vector<int> curr)
{
int sum=0;
for(int i=0; i<int(curr.size()); i++)
sum+=curr[i];

return sum;
}

bool combinationSumutil(set<vector<int> > &res, vector<int> &curr, vector<int> &candidates, int target)
{
// If sum for the current sequence equals target
if(sum(curr)==target)
{
sort(curr.begin(), curr.end());
res.insert(curr);
//return true;
}

// Look for each element in candidate set, each time from start
for(int i=0; i<int(candidates.size()); i++)
{
if(sum(curr)+candidates[i]<=target)
{
curr.push_back(candidates[i]);

// If current+1 call succeeds, then the current decision is right
if(combinationSumutil(res, curr, candidates, target))
return true;

// Undo current decision, if current+1 call fails
curr.pop_back();
}
}

// Backtrack if current call fails
return false;
}

vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
set<vector<int> > res;

vector<int> curr;

combinationSumutil(res, curr, candidates, target);

vector<vector<int> > final(res.begin(), res.end());

return final;
}
};``````

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