Coin Counting / Integer Partition

gistfile1.py

memo = dict()

# Returns a list of lists of all possibilities
def coin_count(amount,poss,curpos):
  if amount == 0:
    return [[]]
  elif amount < 0 or curpos >= len(poss):
    return []
  elif (amount,curpos) in memo: # memoized
    return memo[(amount,curpos)]

  # either use poss[0]
  out = []
  for sublist in coin_count(amount-poss[curpos], poss, curpos):
    out.append( [poss[curpos]] + sublist)

  # or don't use it
  out1 = coin_count(amount,poss,curpos+1)

  # memoize
  memo[(amount,curpos)] = out + out1

  return out + out1

coins = [200,100,50,20,10,5,2,1]
print coin_count(200,coins,0)