Daily Programmer: 5-9-2017 created by tapicella - https://repl.it/Hoet/27

Daily Programmer: 5-9-2017.py

'''
Following up on yesterday... Given a sorted list of distinct integers, write a function that returns whether there *any subset combinations* in the list that add up to 0. For example, you would return true if `[-8, 3, 5, 11]` are in the list, because -8 + 3 + 5 = 0. Also return true if 0 appears in the list.
'''

from itertools import combinations

def findSubset(mylist):
  if len(mylist)==0: return False
  elif len(mylist)==1: return(mylist[0]==0)
  else:
    neg = []
    pos = []
    for n in mylist:
      if n < 0:
        neg.append(n)
      elif n==0: return True 
      else:
        pos.append(n)
    subsums = {}
    for i in range(1, len(neg)+1):
      for comb in combinations(neg, i):
        subsums[(sum(list(comb)))] = list(comb) 
    for i in range(1, len(pos)+1):
      for comb in combinations(pos, i):
        if sum(list(comb))*-1 in subsums:  #Collision strategy suggested by my friend Sol
          #return True 
          return subsums[sum(list(comb))*-1]
    #return False 
    return("No subsets found")
    
print(findSubset([-98634, -86888, -48841, -40483, 2612, 9225, 17848, 71967, 84319, 88875]))
print(findSubset([-83314, -82838, -80120, -63468, -62478, -59378, -56958, -50061, -34791, -32264, -21928, -14988, 23767, 24417, 26403, 26511, 36399, 78055]))