## 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:

,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