how to build the solution in coin change problem?

general
, ,
1

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.

2

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.
    }
}
3

@kashi_sh

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

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

4

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.