Add Operators: Expression Building

Given the string "123" and a target of 6, insert the operators +, -, and * between the digits to form an expression that evaluates to the target. One answer is "1+2+3" = 6. The problem asks you to find all such expressions.

This looks straightforward at first, since you just try every operator in every gap, but multiplication makes it surprisingly tricky. Because binds tighter than + and -, you cannot simply accumulate a running total from left to right. The expression "2+32" equals 8, not 10, and a naive left-to-right evaluation would get it wrong. The entire algorithm hinges on how you handle this precedence issue.

The "Last Operand" Trick

The elegant solution is to carry one extra piece of state through the recursion: the last operand you added or subtracted. This lets you "undo" the previous operation when you encounter a multiplication.

Here is the idea. Suppose you have been evaluating left to right and the current accumulated value is val. The most recent operation added some amount last to reach that value (if the last operation was subtraction, last is negative). Now you encounter a * followed by some number num. Instead of multiplying the entire accumulated value, you need to:

1. Undo the last operation: subtract last from val.
2. Apply the multiplication: add last * num instead.

In code, that is new_val = val - last + last * num. The new "last operand" becomes last * num, because if another multiplication follows, you would need to undo this combined product.

For + and -, the update is simpler. For +, the new value is val + num and the new last is num. For -, the new value is val - num and the new last is -num (negative, so that a subsequent * can undo the subtraction correctly).

Walking Through "232" with Target 8

Let us trace how the algorithm finds "2+3*2" = 8.

We start at position 0 with no operators yet. The first number has no operator before it, so we just pick it. We take "2" as the first number: val = 2, last = 2.

Now we are at position 1 and must choose an operator and a number. We try +:

Take "3" with +: val = 2 + 3 = 5, last = 3. Now at position 2.

Take "2" with : we need to undo the +3 and apply 2 instead. new_val = 5 - 3 + 3 * 2 = 5 - 3 + 6 = 8. last = 3 * 2 = 6. We have reached the end of the string and val = 8 = target, so we record "2+3*2".

Without the last-operand trick, we would have computed 5 * 2 = 10 at the final step. That is wrong, because it multiplies the entire accumulated value instead of just the 3.

Code: Add Operators

def add_operators(num, target):
    res = []

    def bt(i, path, val, last):
        if i == len(num):
            if val == target:
                res.append(path)
            return

        for j in range(i + 1, len(num) + 1):
            s = num[i:j]
            n = int(s)

            # no leading zeros in multi-digit numbers
            if len(s) > 1 and s[0] == '0':
                break

            if i == 0:
                # first number: no operator
                bt(j, s, n, n)
            else:
                bt(j, path + '+' + s, val + n, n)
                bt(j, path + '-' + s, val - n, -n)
                bt(j, path + '*' + s, val - last + last * n, last * n)

    bt(0, '', 0, 0)
    return res

The outer loop for j in range(i + 1, len(num) + 1) controls digit grouping: how many digits to take for the next number. At each grouping, we try all three operators (or no operator for the first number). The recursion bottoms out when we have consumed all digits, and we check whether the accumulated value equals the target.

Leading Zeros

One subtle rule: multi-digit numbers must not have leading zeros. The string "105" can produce "1*05", but "05" is not a valid number. We handle this with the check if len(s) > 1 and s[0] == '0': break. The break (not continue) is intentional: once we have a leading-zero number, taking even more digits will also have a leading zero, so there is no point continuing the loop.

Single-character "0" is perfectly valid. The expression "1+0+5" is fine. It is only multi-digit numbers like "05" or "005" that are illegal.

The Digit Grouping Dimension

What makes this problem combinatorially rich is that you are choosing two things at each step: which operator to use and how many digits to consume for the next number. In "1234", after the first number you might take "2", "23", or "234" as the next operand. Each of those groupings then branches into three operator choices.

This double branching means the search space is larger than it first appears. In a string of n digits, there are $n-1$ gaps. At each gap you have three operator choices, which alone gives $3^{n-1}$ combinations. But digit grouping adds another factor: you are also choosing where to place the boundaries between numbers. The combined effect is roughly $O(4^n)$ in the worst case, though the exact count depends on the structure of the input.

Walking Through "105" with Target 5

This example exposes the leading-zero rule in action. The digits are [1, 0, 5].

Starting at position 0, we pick "1" as the first number: val = 1, last = 1.

At position 1, we try different digit groupings and operators:

Take "0" with +: val = 1 + 0 = 1, last = 0. At position 2, take "5" with +: val = 1 + 5 = 6. Not 5. Try : `val = 1 - 0 + 05 = 1. Not 5. Try -: val = 1 - 5 = -4`. No.

*Take "0" with :* `val = 1 - 1 + 10 = 0, last = 0. At position 2, take "5" with +: val = 0 + 5 = 5`. That is the target. Record "1*0+5".

Take "05" as a two-digit number: This has a leading zero. The loop breaks: "05" is not a valid number, and neither would "050" or any longer prefix starting with 0.

Take "0" with -: val = 1 - 0 = 1, last = -0 = 0. Position 2, take "5" with +: val = 1 + 5 = 6. Try -: val = 1 - 5 = -4. Try : `val = 1 - 0 + 05 = 1`. None work.

Also from position 0, we can take "10" as the first number: val = 10, last = 10. Then at position 2, take "5" with +: 15. With -: 5. Record "10-5". With *: 50. No.

And "105" as the first number: val = 105. Not equal to 5. Done.

The final answers are *["10+5", "10-5"]*. The leading-zero rule correctly blocked "105" while allowing "1*0+5" (where "0" is a valid single-digit number).

Walking Through "232" with Target 8: Multiple Solutions

The string "232" with target 8 actually has two solutions: "23+2" and "2+32". Let us trace both to see the last-operand trick handle chained multiplications correctly.

*Path 1: "23+2".* Start with "2": val = 2, last = 2. Take "3" with `: new_val = 2 - 2 + 23 = 6, last = 23 = 6. Take "2" with +: val = 6 + 2 = 8`. Match, so record "2*3+2".

*Path 2: "2+32".* Start with "2": val = 2, last = 2. Take "3" with +: val = 2 + 3 = 5, last = 3. Take "2" with `: new_val = 5 - 3 + 32 = 8, last = 32 = 6`. Match, so record "2+3*2".

Notice how the two paths reach the same value through completely different evaluation orders. In Path 1, the * happens first, so last becomes the product 6 before the trailing + is applied. In Path 2, the * happens last, and the trick rolls back the most recent +3 before applying the multiplication. In both cases, val correctly reflects standard precedence at every step.

Chained Multiplications

The trick really earns its keep when multiplications chain. Consider "232" with target 12: the expression "232" evaluates to 12. Trace: start with "2": val = 2, last = 2. Take "3" with *: new_val = 2 - 2 + 2*3 = 6, last = 6. Take "2" with *: new_val = 6 - 6 + 6*2 = 12, last = 6*2 = 12. Each multiplication folds into the existing last, so a chain like a*b*c*d is evaluated as a single contiguous product attached wherever the last + or - left off. That is precisely how operator precedence works.

Connection to Expression Evaluation

It is worth noting that this problem is the inverse of expression evaluation. In evaluation, you are given a fully formed expression like "2+3*2" and must compute its value (respecting operator precedence). Here, you are given digits and a target value, and must build the expression. The last-operand trick is essentially inlining a mini-evaluator into the backtracking: you evaluate the expression as you build it, maintaining just enough state (val and last) to handle precedence correctly without needing to parse the expression after the fact.

Complexity Analysis

Time: At each of the $n-1$ gaps between digits, we branch into three operators, and at each position, we also choose how many digits to group into the next number. The total number of recursive paths is $O(4^n)$ in the worst case. Each path does $O(n)$ work to build the expression string, so the total time is $O(n \cdot 4^n)$.

Space: The recursion stack goes at most n levels deep (one level per digit), so the stack space is $O(n)$. The expression string being built is also at most $O(n)$ in length. The output list can hold up to $O(4^n)$ expressions, each of length $O(n)$, but that is output-dependent space; the algorithm itself uses $O(n)$ working space.

Recognizing this pattern

You're probably looking at expression-building backtracking when:

• You insert +, -, or * between digits of a string to reach a target value.
• The input is a short digit string, typically length ≤ 10, and a target integer.
• Operator precedence matters, so naive evaluation after the fact is awkward.
• Phrasing mentions "all expressions that evaluate to target" or "ways to insert operators".

Common templates:

• Last-operand carry: recurse with (value, last_operand) to handle * precedence inline. Example: Expression Add Operators.
• All split points: at each step, try every prefix as the next number, including leading-zero skip. Example: Expression Add Operators.
• Parenthesized evaluation: split the expression at each operator and combine sub-results. Example: Different Ways to Add Parentheses.
• Target-equation construction: backtrack over operator choices to satisfy a numeric goal. Example: Target Sum.