## Editorial for Summer Institute '17 Contest 1 P8 - Mo' Money

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: d, Kirito

There are three possible solutions to this problem:

##### Solution 1 — Dynamic Programming

This problem can be solved with dynamic programming. Let be the number of ways to get with the first coins. Initially, . Thus our DP state transition is , where is the value of the coin.

Time Complexity:

##### Solution 2 — Brute Force

Notice that is rather small. Thus we can generate all subsets of the coins, and count how many of these subsets sum to .

Time Complexity:

##### Solution 3 — Recursion

Write a recursive function that has two parameters, the current index and the sum so far. This function will iterate through all subsets of the coins.

Time Complexity:

## Comments

There are no comments at the moment.