# 20 ms concise solution with explanation.

• Concise solution. 20 ms solution.
The algorithms is as follows:

1. From the start of the array, make two decisions at the same time (recursive calls)
a) Pick the current position as a part of the possible solution, decrement the counter and recurse.
b) Move to the next position and start again. (Ignoring the position with which we started)

Eg. for (2,3,4,5) 5

In step a pick 2, change the target to 5 -2 and recurse.
In step b) ignore the first position (decision of not including it at all) and move on.

These two when recursed cover all possible combinations.

``````class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>>sumset;
vector<int> curset;
//for(auto i = candidates.begin(); i < candidates.end(); ++i)
sumgame(candidates.begin(), target, candidates, curset, sumset);
return sumset;
}

void sumgame(auto i, auto target, auto &candidates, vector<int> &curset, auto &sumset)
{
//check for the terminating condition and return if the end of the vector is reached.
if(i == candidates.end())
return;
//recurse while leaving out the current position candidate. This covers half of the branches of the program.
// Each time the function is called, it makes both decisions at the same time.
sumgame(i+1, target, candidates, curset, sumset);
// the following conditions can be shortened at thecost of readability, so not doing it.
if(target - *i == 0)
{
curset.push_back(*i);
sumset.push_back(curset);
curset.pop_back();
}
if(target - *i > 0)
{
curset.push_back(*i);
sumgame(i, target - *i, candidates, curset, sumset);
curset.pop_back();
return;
}

}

};
``````

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