Expression Add Operators

Expression Add Operators asks you to slot +, -, and * between the digits of a string so the expression evaluates to a target. It is a classic backtracking problem with one nasty twist: multiplication breaks the simple running-total trick, so you have to carry an extra piece of state.

The slow way first

You could generate every possible expression as a string, then evaluate each one. With n digits there are 3 choices in each of the n - 1 gaps, so that is exponential — and re-evaluating each full string from scratch is wasteful. We want to compute the value as we build, and prune nothing we do not have to.

The real question: can I keep a running total as I add each operand? For + and -, yes. For *, no — because * binds tighter than the +/- already baked into the total.

The idea: carry total and prev

Walk the string left to right. At each position pick the next operand (a slice of digits), then branch on the operator:

• + operand → total + operand, and the new prev is +operand.
• - operand → total - operand, and the new prev is -operand.
• * operand → here is the trick. We must undo the last operand from the total and re-add it multiplied: total - prev + prev * operand. The new prev is prev * operand.

prev is the value the previous operand contributed, so * can roll it back and replace it with the product.

When we reach the end of the string, if total equals target we record the expression we built.

Walk through it

Step through the animation on num = "123", target 6. We take 1, then choose * twice. Watch prev lead the way: after 1*2, total and prev are both 2; after 1*2*3, the * undoes prev (2) and re-adds 2*3 = 6, so total becomes 6. At the end of the string, total equals target, so 1*2*3 is recorded.

Pseudocode

dfs(index, expr, total, prev):
    if index == end of string:
        if total == target: record expr
        return
    for each operand slice starting at index:
        cur = value of slice
        if index == 0:                       # first operand: no operator
            dfs(next, slice, cur, cur)
        else:
            dfs(next, expr + "+" + slice, total + cur,  cur)
            dfs(next, expr + "-" + slice, total - cur, -cur)
            dfs(next, expr + "*" + slice, total - prev + prev*cur, prev*cur)

The Python solution

def add_operators(num, target):
    res = []
    def dfs(i, expr, total, prev):
        if i == len(num):
            if total == target:
                res.append(expr)
            return
        for j in range(i, len(num)):
            cur = int(num[i:j + 1])
            s = num[i:j + 1]
            if i == 0:
                dfs(j + 1, s, cur, cur)
            else:
                dfs(j + 1, expr + "+" + s, total + cur, cur)
                dfs(j + 1, expr + "-" + s, total - cur, -cur)
                dfs(j + 1, expr + "*" + s, total - prev + prev * cur, prev * cur)
    dfs(0, "", 0, 0)
    return res

• dfs(i, expr, total, prev) tracks where we are, the string so far, the running value, and the previous operand contribution.
• The base case (line 4) fires at the end of the string; we record expr only if total == target.
• The inner for j loop picks the next operand cur, allowing multi-digit numbers like "12".
• i == 0 is the first operand, which takes no operator — prev starts equal to cur.
• Line 17 is the heart: * undoes prev from the total and re-adds prev * cur, and passes prev * cur as the new prev so a later * can chain correctly.

Complexity

There are n - 1 gaps and roughly four choices at each (+, -, *, or extend the number), so the search tree is about O(4^n). Each leaf does O(n) work to assemble its string. Recursion depth — and the expression string — is O(n).

When this pattern shows up

Practice