Money Change Problem

#1


only one test case clear. please help me to figure out what’s wrong going on.

#2

explain your logic…

#3

i am creating all possible set of a[i] from array that give me N. For N = 4 .
set = {1,1,1,1}, {1,1, 2}, {1,3}, {2, 2}
and above set count = 4

#4

you cannot create 2^500 sets.
1st analyze time complexity of your code before writing anything. It will only waste your time.

#5

void solve(int N, vector&v, int j){
///base case
if(N == 0){
///total number of way to reach zero will be the ans
cnt++;

    return;
}

///discard case when N became negative
if(N < 0){

    return;
}

for(int i = j; i < m; i++){

///decrement N coins of array to reduce zero.
solve(N-a[i], v, i);
}
}

#6

i think you are getting wrong. i am not creating 2^500 sets. i am maintaining possible configurations such than N reduce to zero increment cnt by 1.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like
#8

@Robin_rst have a look .

#9

top down dp solution

#10

@rajujnvgupta
Refer this bottom-up approach.
Just convert it into top down.

#11

i did but still not fail for some test case.