demo.py

# Recursively check all combinations with +-
def check(step, acc, ops, digits):
    if step >= len(digits):
        if acc == 100:
            row = ''

            for pair in zip(digits, ops):
                row += '%s %s ' % pair

            print '%s%s' % (row, digits[-1])
    else:
        check(step + 1, acc + digits[step], ops + ['+'], digits)
        check(step + 1, acc - digits[step], ops + ['-'], digits)


# Generate all possible numbers
def calc(digit, s):
    acc = 0

    for n in xrange(digit, 10):
        # Accumulate 1, 12, 123, 1234 based on a current digit
        acc = acc * 10 + n

        # Store number in a history
        history = s + [acc]

        # Recursively process all combinations
        calc(n + 1, history)

    # Check results
    if s:
        check(1, s[0], [], s)


if __name__ == '__main__':
    calc(1, [])