#!/usr/bin/python3 # # This program reads a string of digits S as a command-line argument, # and inserts plus (+) and minus signs (-) in the sequence of digits # so as to create an expression that evaluates to zero. The program # should output a resulting expression, if one such expression exists, # or "None" if no such expression exists. # # For example, if S is "201015900001", then the program could output # "+2+0+10+1-5-9+0+0+0+0+1". Instead, if S is "200015800001", then the # program should output "None". # # This program tends to produce long expressions (with many operands). # import sys def solve_puzzle(s, n): v = int(s) if v == n: return '+' + s if v == -n: return '-' + s if v < abs(n): return None for i in range(1,len(s)): front = s[0:i] back = s[i:] target = int(front) back_solution = solve_puzzle(back,n-target) if back_solution != None: return '+' + front + back_solution back_solution = solve_puzzle(back,n+target) if back_solution != None: return '-' + front + back_solution return None print(solve_puzzle(sys.argv[1],0))