# countSums.py 
# input: 115 seeds.txt


from reader import *

def countSumsR(nums, tot):
  return countSums(nums, tot, len(nums))

def countSums(nums, tot, n):
  if tot < 0:
    return 0
  elif (tot == 0) or (n == 0):
    return 1
  else:
    return countSums(nums, tot, n-1) + \
           countSums(nums, tot-nums[n-1], n-1)

def countSums2D(nums, tot):
  # tots[i][j]
  n = len(nums)
  tots = [[0 for j in range(tot+1)] for i in range(n+1)]   
  for j in range(tot+1):    # set first row
    tots[0][j] = 1
  for i in range(1, n+1):   # set d's for other rows
    d = nums[i-1]
    for j in range(d):
      tots[i][j] = tots[i-1][j]
    for j in range(d,tot+1):
      tots[i][j] = tots[i-1][j] + tots[i-1][j-d]
  return tots[n][tot]

def countSums1D(nums, tot):
  n = len(nums)
  tots = [1]*(tot+1)
  for i in range(1,n+1): 
    d = nums[i-1]
    for j in range(tot, d-1, -1):
      tots[j] += tots[j-d]
  return tots[tot]


if __name__ == "__main__":
  nums = [6, 8, 14, 16, 23, 24, 28, 29, 41, 48, 49, 56, 60, 67, 75]
  tot = 115
  print("----- Recursive -----")
  print(countSumsR(nums, tot))
  print("----- Iterative 2D -----")
  print(countSums2D(nums, tot))
  print("----- Iterative 1D -----")
  print(countSums1D(nums, tot))