# Homework Help: Subset sum counting

1. Dec 27, 2011

### martix

1. The problem statement, all variables and given/known data
How many different ways can £2 be made using any number of coins?
(In other words, how many ways can you obtain the sum of 200 with terms from the following finite set - 200, 100, 50, 20, 10, 5, 2, 1. Order does not matter.)

2. Relevant equations
None?

3. The attempt at a solution
No idea.
I've been mulling over this problem for way too much time now without producing anything viable.
A PnP solution is beyond me at this point. On the computational side I've been thinking of a recursive solution which should spawn this massive recursion tree and I'm pretty sure there's gotta be a better method out there.

2. Dec 27, 2011

### micromass

Do you know generating functions??

3. Dec 27, 2011

### martix

Nope...
First time I've heard of those. I can always read up on them if they are relevant to the solution.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook