What is the best technique to solve the coin change problem.

I have been given N coins and given there denominations, and a number K. I want to calculate all the subsets of N that can make the sum of K. I know the solution using Bit masking technique but, since it takes the exponential time it will not be good for N>=20 so is there any other faster way to nail this problem.

hey What do you mean by subsets if duplicate denomination are allowed then maybe this recurrence can help you

          Rec(Pos, Sum) ---:   Rec(Pos + 1, Sum) 

                                        +

                                 Rec(Pos + 1, Sum - Array[Pos])  IF Sum >= Array[Pos]

Call this function Rec(0, K) and Array contain denominations now you have to do 2 work
(i) Define Base Condition
(ii) Memorize it :slight_smile:

If still didn’t get you can ask

//