# sumSubsets.py

'''
  https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution
'''

import itertools


def sumSubsetsR(nums, tot):
  combs = sumSubsets(nums, tot, 0, [])
  return sorted(combs, key=sum)

def sumSubsets(nums, tot, idx, comb):
  # recursive
  sumC = sum(comb)
  if sumC == tot:
    return [comb]
  elif sumC > tot:
    return []
  else:
    combs = [comb]
    for i in range(idx, len(nums)):
      combs.extend(sumSubsets(nums,tot,i+1,comb+[nums[i]]))
    return combs

def sumSubsetsD(nums, tot):
  dp = {0: [[]]}   # sum : list of combs summing to value
  for num in nums:
    # print("dp", dp)
    # print("num", num)
    # build temp dict using num
    tempDict = {}
    for sumK in dp.keys(): 
      # try to extend the existing sums from dp
      nSum = sumK + num
      if nSum <= tot:
        # modify every list associated with the old sum
        nCombs = [comb + [num] for comb in dp[sumK]]
        tempDict[nSum] = tempDict.get(nSum, []) + nCombs
    # print("tempDict", tempDict)
    for k in tempDict.keys():
      # merge temp with dp
      comb = dp.get(k,[])
      dp[k] = comb + tempDict[k]
  # convert dp dict into a list of lists
  combs = []
  for cmbs in dp.values():
    combs.extend(cmbs)
  return sorted(combs, key=sum)

def sumSubsetsC(nums, tot):
  # Using itertools.combinations
  combs = [list(comb) for r in range(len(nums)+1)
                 for comb in itertools.combinations(nums, r)
                    if sum(comb) <= tot]
  return sorted(combs, key=sum)

if __name__ == "__main__":
  nums = [2, 2, 3, 5, 6, 8]
  tot = 8
  print("----- Recursive -----")
  print(sumSubsetsR(nums, tot))
  print("----- Dict -----")
  print(sumSubsetsD(nums, tot))
  print("----- Itertools -----")
  print(sumSubsetsC(nums, tot))