Problem 76

p76.py

def Partition(goal, alist):
  ways = [1] + [0] * (goal)
  for options in alist:
     for i in range(len(ways) - options):
        ways[i + options] += ways[i]
  return ways[-1]-1 

'''
Sample Output for partitioning 5:

Current Table [1, 0, 0, 0, 0, 0]
Current number being checked 2
Current i: 0
Current i: 1
Current i: 2
Current i: 3

Current Table [1, 1, 1, 1, 1, 1]
Current number being checked 2
Current i: 0
Current i: 1
Current i: 2
Current i: 3

Current Table [1, 1, 2, 2, 3, 3]
Current number being checked 3
Current i: 0
Current i: 1
Current i: 2

Current Table [1, 1, 2, 3, 4, 5]
Current number being checked 4
Current i: 0
Current i: 1

Current Table [1, 1, 2, 3, 5, 6]
Current number being checked 5
Current i: 0

Total number of ways to partition 5 is 6
'''