Write a program that outputs all possibilities to put +, - or nothing between the numbers 1, 2...9 (in this order) such that the result is always 100. For example, 1+2+34-5+67-8+9

gistfile1.py

from math import pow

def find_all_numbers():
    # this is the loop of numbers 1,2...9
    for x in range(1, 10):
        # build a dict with each number as a key;
        # 1: [1, 12, 123, ...]
        numbers[x] = []
        # loop to increase multiplier which is a power of 10;
        # 1*10^0, 1*10^1, ...
        for y in range(0, 10-x):
            # add the pos and neg values to the list for this dict item
            numbers[x].append(int(build_number(x, pow(10, y))))
            numbers[x].append(int(build_number(x, pow(10, y)) * -1))


def build_number(n, multiplier):
    """ Recursive method to build a number composed of
        consecutive digits multiplied by a power of 10.
       100000000 
      + 20000000 
       + 3000000 
        + 400000 
         + 50000
           + 600 
           + 700 
            + 80 
             + 9
       ---------          
       123456789
    """
    # base case to return the right most digit
    if multiplier == 1:
        return n * multiplier
    # recursively compute the number by multiplying this digit
    # by multiplier and adding it to the next digit times 10^multiplier-1
    else:
        return (n * multiplier) + build_number(n+1, multiplier/10)


def find_all_paths(graph, start, end, path=[], max_length=10):
    """ Depth first traversal of graph to find number sets 1-9. """
    if len(path) >= max_length:
        return []
    path = path + [start]

    if start >= 1:
        last_digit = start % 10
    else:
        last_digit = 10 - (start % 10) 

    if last_digit == end:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        paths += find_all_paths(graph, node, end, path, max_length=max_length)
    return paths


def sum_100(number_set):
    """ Tests if sum of list is 100. """
    return sum(number_set) == 100;

def pretty_print(h_sets):
    """ Print the number sets in the required format: 1 + 2 - 3 ... 
        rather than a list of ints. """
    for h in h_sets:
        print ''.join([('+' if n>0 and str(n)[0] != '1' else '') + str(n) for n in h])


numbers = {}
find_all_numbers()
number_sets = {}

# convert the set of numbers to a graph like dict.
# key is number.  value is list of possible subsequent numbers.
# 1 : [2, 23, 234, 2345, ....] """

for key, value in numbers.iteritems():
    for v in value:
        if v >= 1:
            last_digit = v % 10
        else:
            last_digit = 10 - (v % 10)

        if last_digit == 9:
            number_sets[v] = []
        else:
            number_sets[v] = numbers[last_digit+1]

# all sets that equal 100
hundreds = [p for p in find_all_paths(number_sets, 1, 9) if sum_100(p)]
# print them in the required format
pretty_print(hundreds)