Return all valid expressions with specific target

The problem is stated as: Given a string that contains only digits 0-9 and a target value, return all expressions that are created by adding some binary operators (+, -, or *) between the digits so they evaluate to the target value. In some cases there may not be any binary operators that will create valid expressions, in which case the function should return an empty array. The numbers in the new expressions should not contain leading zeros.

The function should return all valid expressions that evaluate to target, sorted lexicographically.

For example:

digits = "123" and target = 6, should return: ["123", "1+2+3"]

My current algorithm is below. I optimized it as much as I can. The question is base on code fights. My algo will generate all combinations of operands and operators accordingly. For the example above, it'll generate:

Operands:

[['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]

Operators:

{0: [()], 1: [('+',), ('-',), ('*',)], 2: [('+', '+'), ('+', '-'), ('+', '*'), ('-', '+'), ('-', '-'), ('-', '*'), ('*', '+'), ('*', '-'), ('*', '*')]}

It then combines all possible combinations of operands and operators and evaluate each.

For digits = "1234506789" and target = 6, it takes about 2.2 secs. It should be enough for code fights that has a limit of 4 sec, but I guess that also depends on the speed of the processor. But for some reason it still hits the time limit from the site. Thus Im trying to see how it can be optimized a bit more.

Restrictions are:

2 <= digits.length <= 10
-10^4 <= target <= 10^4

My code is below. I commented out some of the alternatives I used, which pretty much has the same speed though.

```
from itertools import combinations, permutations
import itertools
import time

def getExpression(digits, target):

operation = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'': lambda a, b: a b,
}

seen = {}

def calculate2(e,sign):

• Separation of concerns is an important design goal, and you have aimed for that by separating the generation of expressions from their evaluation. However, this slows you down compared to a more direct approach that updates partial results while exploring the possibilities.

• Evaluating each expression separately does not allow you to exploit similarities between expressions.

• Sorting the results can be avoided by exploring the possibilities in lexicographic order to begin with.

• Timing is best handled by the timeit module. To focus on the performance of the algorithm itself, do not print while timing.

The problem lends itself to a concise recursive solution that runs in 0.22 s while your version takes 2.6 s on my computer:

def expressions(digits, target, k=1):
    """Generate all expressions that evaluate to target
    using given digits and operators *,+,-, while multiplying first term by k
    """
    for i in range(1, len(digits)):
        left = digits[:i]
        right = digits[i:]
        n = k * int(left)
        for e in expressions(right, target, n):
            yield left + '*' + e
        for e in expressions(right, target - n):
            yield left + '+' + e
        for e in expressions(right, target - n, -1):
            yield left + '-' + e
        if left == '0': # catch leading zero
            return
    if k * int(digits) == target:
        yield digits

if __name__ == '__main__':
    import timeit     

    digits = "1234506789"
    target = 6
    print(timeit.repeat(lambda : list(expressions(digits, target)), number=1))

StackExchange Code Review Q#162944, answer score: 6