After a bit of thinking, I came up with this Python solution.

The whole solution tree is explored, but if the value of a partial expression is found to be bigger than the target, the branch is closed, and children are not evaluated.

All solutions are printed, not just one.

To work correctly with operator precedence, and to avoid re-evaluating the whole expression at each step, you are forced to represent a partial expression as a (sum + product * int)

For the record, the aim of the code is to be clear and readable, not to be the most efficient hacked-tricky code that is the fastest. Pythonistas, if something can be improved to be clearer, please do tell me ;) (in particular, I am not so fond of the deepcopy..)

```
import copy
class Calculator(object):
"""
Representing a simple calculator.
As you enter digits or operators, it computes
the value of the resulting expression.
An expression is always represented as:
sum + product * number
"""
def __init__(self, value):
"""
@type value: str
"""
n = int(value)
self.sum = 0
self.prod = 1
self.num = n
# value of expression
self.value = n
# string representation
self.repr = value
def __str__(self):
return self.repr
def getvalue(self):
return self.value
def operation(f):
"""
decorator recalculating the value of the expression
after an operation.
It works on a deepcopy to avoid changing the value,
and returns the newly created object.
"""
def decorated(self, digit):
deepcopy = copy.deepcopy(self)
f(deepcopy, digit)
deepcopy.value = deepcopy.sum + deepcopy.prod*deepcopy.num
return deepcopy
decorated.func_name = f.func_name
decorated.func_doc = f.func_name
return decorated
@operation
def digit(self, digit):
"""
@type digit: str
"""
self.repr += digit
self.num *= 10
self.num += int(digit)
@operation
def add(self, digit):
"""
@type digit: str
"""
self.repr += '+' + digit
self.sum = self.sum + self.prod * self.num
self.prod = 1
self.num = int(digit)
@operation
def mult(self, digit):
"""
@type digit: str
"""
self.repr += '*' + digit
self.prod *= self.num
self.num = int(digit)
def solve(input, target):
"""
@type input: str
@type target: int
"""
if not input:
print 'No Solution.'
return
calc = Calculator(input[0])
thislevel = dict()
thislevel[calc.getvalue()] = [calc]
for digit in input[1:]:
nextlevel = {}
for nodes in thislevel.itervalues():
for node in nodes:
for op in (node.digit, node.add, node.mult):
child = op(digit)
val = child.getvalue()
if val <= target:
nextlevel.setdefault(val,[]).append(child)
thislevel = nextlevel
try:
for node in thislevel[target]:
print node
except KeyError:
print 'No Solution.'
solve("1231231234", 11353)
solve("3456237490", 1185)
```