# how to build the solution in coin change problem?

I have one array of size n that represents the denomination of coins(each coin can be used multiple times) and a number k. Now I want to find if the K can be generated using the given denomination and if yes print any one possible solution and if not print NIL. Anyone please help me to code this.

Well, If you just need a solution you can try a simple recursive solution,
something like

``````BOOL isvalid( int sum) {
if( sum ==0)
return 1;
else
return isvalid(sum-a1) || isvalid(sum-a2) ||  isvalid(sum-a3).. and so on for all denominations.
}
``````

To improve the complexity you can add cache.

``````bool arr[sum] = {-1}

BOOL isvalid( int sum) {
if(arr[sum] != -1)
return arr[sum]

if( sum ==0)
return 1;
else {
Bool ans =  isvalid(sum-a1) || isvalid(sum-a2) ||  isvalid(sum-a3).. and so on for all denominations.
if ans == 0
arr[sum] = 0;
else
arr[sum] = 1   // actually you can also terminate method here as you have one valid combination.
}
}``````

@kashi_sh

return isvalid(sum-a1) || isvalid(sum-a2) || isvalid(sum-a3)…

please clarify this statement, or please provide the code if you can.

Here, I want to tell you the main idea …

Let f(i, j)be the number of ways of reaching sum i by using at most j-th coin.

First observation is that f(0, j) = 1, for all j.

Otherwise,

we have two options … either we use the j-th coin or don’t use the j-th coin.

If i < value[j], then we have only one option —

f(i, j) = f(i, j - 1)

Otherwise,

f(i, j) = f(i, j - 1) + f(i - value[j], j) [First time we don’t use the j-th coin, second time, we do.)

Here is a program that uses the idea on my GitHub.

Here is another time I used coin change … But optimised for space.

I have also posted some explanations of these ideas on my GitHub … Just explore it a bit and follow me and star the repository if you want to keep track of further updates.

//