gistfile1.py

from __future__ import print_function

def inverse_coinstar(coins):
  N = len(coins)
  value = sum(coins)
  
  memo = {}
  # ways to make n from coins[:i]
  def ways_to_make(n, i):
    if n == 0:
      return 1
    if n < 0 or i == 0:
      return 0
    
    result = ways_to_make(n, i-1) + ways_to_make(n - coins[i-1], i-1)
    memo[n, i] = result
    return result
  
  if value % 2 == 0:
    return ways_to_make(value / 2, N)

  return 0
  
test_cases = [[1, 1], [1, 1, 1, 1], [2, 3]]

for test in test_cases:
  print(test, inverse_coinstar(test))