Greedy O(n) solution


#1

vector Solution::solve(int A, vector &B)
{
int mn=B[0];vector v;
for(int i=1;i<B.size();i++) mn=min(mn,B[i]);
int num=A/mn;int y=num;
for(int i=0;i<B.size();i++)
{
if((A-B[i])>=0 && (A-B[i])/mn>=num-1)
{
v.push_back(i);
A=A-B[i];
num–;i–;
}
if(v.size()==y) return v;
}
return v;
}


#2

Your code will fail for this input
A : 36
B : [ 2, 13, 11, 17, 18 ]
because you are predicting your answer based on the minimum element