Easy intuitive solution


#1

void helper(vector &A, vector<vector> &out, int start, vector &temp, int target, int B)
{
if(target==0)
{
out.push_back(temp);
return ;
}
if(target<0) return;
if(start==A.size()) return;
int sum=0, count=0;
while(sum<=target)
{
sum+=A[start];
temp.push_back(A[start]);
helper(A, out, start+1, temp, target-sum, B);
count++;
}
while(count–) temp.pop_back();
helper(A, out, start+1, temp, target, B);
}
vector<vector > Solution::combinationSum(vector &A, int B)
{
vector<vector> out;
if(A.size()==0) return out;
sort(A.begin(), A.end());
vector unique;
for(int i=0; i<A.size(); i++)
{
if(i==0||A[i]!=A[i-1]) unique.push_back(A[i]);
}
vector temp;
helper(unique, out, 0, temp, B, B);
if(out.size()<=1) return out;
sort(out.begin(), out.end());
return out;
}