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

If still didnâ€™t get you can ask