22ms C++ solution

• ``````class Solution {
public:
void combinationSum_Recur(vector<vector<int> > &buf, int cur,
int target, vector<int> &piece, vector<vector<int> > &ans)
{
if(cur == target)
{
ans.push_back(piece);
}
int last = 0;
if(piece.size()>0)last = piece.back();
for(int i = 0; i < buf[cur].size(); i ++)
{
int step = buf[cur][i];
if(step < last)break; // the solution must be ascending
piece.push_back(step);
combinationSum_Recur(buf, cur + step, target, piece, ans);
piece.pop_back();
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector<vector<int> > ans;
if(target < 1)return ans;
int C = candidates.size();
sort(candidates.begin(), candidates.end());
vector<vector<int> > buf;
for(int i = 0; i <= target; i ++)
{
buf.push_back(vector<int>());
}
for(int i = C-1; i >= 0; i --)
{
int step = candidates[i];
if(target >= step)
{
buf[target - step].push_back(step);
}
for(int j = target - 1; j >= step; j --)
{
if(buf[j].size()>0)
{
buf[j-step].push_back(step);
}
}
}
if(buf[0].size()<1)return ans;
vector<int> piece;
combinationSum_Recur(buf, 0, target, piece, ans);
return ans;
}
};``````

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