RosettaCode: Sum to 100

Hmhz-18.py

'''
rosettacode.org/wiki/Sum_to_100
brute force solution
https://repl.it/Hmhz/20
'''

# http://stackoverflow.com/questions/34559663/convert-decimal-to-ternarybase3-in-python
def decimalToTernary (n):
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = divmod(n, 3)
        nums.append(str(r))
    return ''.join(reversed(nums))
    
def ternaryToDecimal (n):
    return int(str(n), 3)
    
t = decimalToTernary
d = ternaryToDecimal

def findSolutions(target):
  ''' 
  Encode all possible configurations in ternary. Examples:
  000000000 represents -1-2-3-4-5-6-7-8-9
  111111100 represents +1+2+3+4+5+6+7-8-9
  222222222 represents 123456789
  '''
  possibilities = d(222222222) #19682.  
  results = []
  all_totals = {}
  for i in range(possibilities):
    i_signs = t(i)
    s_signs = (str(i_signs).zfill(9))
    start = "123456789"
    total = 0
    stack = ""
    metastack = ""
    if s_signs[0] == '1':
        continue; # +123456789 is equivalent solution to 123456789, etc
    for s in range(len(s_signs)):
      if s_signs[s] == '0': 
        if(len(stack)!=0):
          total += int(stack)
          metastack += stack
          stack = ""
        stack += "-"
      elif s_signs[s] == '1':
        if(len(stack)!=0):
          total += int(stack)
          metastack += stack
          stack = ""
        stack += "+"
      stack += str(start[s])
    total += int(stack)
    metastack += stack
    if total == target:
      results.append(metastack)
    if total in all_totals:
      all_totals[total] = all_totals[total]+1
    else:
      all_totals[total] = 1
  return results, all_totals

''' Show all solutions that sum to 100  '''
target_sum = 100
solutions, all_sums = findSolutions(target_sum)  
print("Number of solutions for sum to %d: %d %s" % (target_sum, len(solutions), str(solutions)))

''' Show the sum that has the maximum number of solutions (from zero to infinity*) (123456789) '''
max_sol = -1
max_sum = -1
for j in all_sums:
  if all_sums[j] > max_sol and j >= 0:
    max_sol = all_sums[j]
    max_sum = j
  
print("The sum with the maxiumum number of solutions (%d) is %d" % (max_sol, max_sum))

''' Show the lowest positive sum that can't be expressed (has no solutions), using the rules for this task '''
for k in range(123456790):
  if k not in all_sums:
    print("The lowest positive sum with no solutions is %d" % k)
    break;

''' Show the ten highest numbers that can be expressed using the rules for this task   (extra credit) '''
sort_sums = sorted(all_sums.keys())
print("The ten heightest sums are %s" % str(sort_sums[-10:]))