Expression Add Operators

Table of Contents +

You get a string of digits like 123. You may slide a plus, a minus, or a times between any two digits, or leave them stuck together as one number. The question asks for every way that the final math equals a target. The twist is the times sign. Times must happen before plus and minus, so you cannot just add things up as you go. That precedence rule is the whole challenge.

🎯 The Problem

You get a string of digits and a target. You insert operators between digits and keep the expressions that equal the target.

The rules:

  • At each gap you may place +, -, or *, or keep digits glued as one number.
  • A number cannot have a leading zero unless the number is just 0. So 05 is not allowed.
  • Times binds tighter than plus and minus. Multiplication happens first.
  • Return every expression whose value equals the target, in any order.
Input:  num = "123", target = 6
Output: ["1+2+3", "1*2*3"]


Explanation: 1 + 2 + 3 = 6 and 1 * 2 * 3 = 6

This diagram shows the choices at each gap between digits. At every gap we pick an operator or we glue the digits together.

+ or - or * or glue

+ or - or * or glue

1

2

3

check if value == 6

🐢 Approach 1: Build Every String Then Evaluate (Brute Force)

The idea:

  • Place an operator or nothing in each gap.
  • Build every possible expression string.
  • Run a full math evaluator on each finished string.
  • Keep the strings whose value matches the target.

Why it is weak:

  • You build the whole string before you know it is hopeless.
  • Writing a correct evaluator that respects precedence is its own tricky task.
  • You parse each finished string from scratch.
  • So the same multiplication work happens again and again.

Here is the build-then-evaluate code for that idea:

expression_add_operators_brute_force.py
def add_operators(num, target):
    result = []


    def build(index, expr):
        if index == len(num):
            if eval(expr) == target:
                result.append(expr)
            return
        for end in range(index + 1, len(num) + 1):
            piece = num[index:end]
            if len(piece) > 1 and piece[0] == "0":
                break
            if index == 0:
                build(end, piece)
            else:
                for op in "+-*":
                    build(end, expr + op + piece)


    build(0, "")
    return result

⚡ Approach 2: Backtracking With a Running Value (Best)

The idea in one line: try each operator at each gap, carry the running total as you go, and never parse the string again.

How backtracking works here:

  • Try one operator at a position.
  • Go deeper. Then undo and try the next operator.
  • Carry the current total with you instead of waiting for the end.

Why we keep the last operand:

  • The last operand is the most recent number added or subtracted.
  • Times binds tighter than plus and minus.
  • So a plain total is not enough.
  • When the next operator is times, we must undo the last add and redo it with the multiplication.

The update rule:

  • Add: total becomes total + num, last operand becomes +num.
  • Subtract: total becomes total - num, last operand becomes -num.
  • Multiply: total becomes total - last + (last * num), last operand becomes last * num.
  • This single trick gives correct precedence with no parser.

Leading zero rule:

  • If a chunk starts with 0 and has more than one digit, stop.
  • That blocks numbers like 05.

This diagram shows the running value math for 1*2*3. The last operand carries the multiplication forward.

take 1: total=1, last=1

see *2: total = 1 - 1 + (1*2) = 2, last=2

see *3: total = 2 - 2 + (2*3) = 6, last=6

end, total == 6, keep 1*2*3

Steps to Solve

  1. Start at position zero with an empty expression, a total of zero, and a last operand of zero.
  2. At the current position, try every chunk of digits as the next number, stopping if it has a leading zero.
  3. If this is the first number, just take it as the start of the total and the last operand.
  4. Otherwise try plus, minus, and times in turn.
  5. For plus and minus, update the total and set the last operand to the signed number.
  6. For times, undo the last operand and fold the multiplication into the total.
  7. When you reach the end of the string, if the total equals the target, save the expression.

This Python version carries the running total and the last operand through the recursion, so it never parses the string again.

expression_add_operators.py
def add_operators(num, target):
    results = []


    def backtrack(pos, total, last, expr):
        if pos == len(num):
            if total == target:        # full string used and value matches
                results.append(expr)
            return
        cur = 0
        for i in range(pos, len(num)):
            if i > pos and num[pos] == "0":
                break                  # no leading zero in a multi-digit chunk
            cur = cur * 10 + int(num[i])
            chunk = num[pos:i + 1]
            if pos == 0:
                # first number has no operator in front of it
                backtrack(i + 1, cur, cur, chunk)
            else:
                backtrack(i + 1, total + cur, cur, expr + "+" + chunk)   # plus
                backtrack(i + 1, total - cur, -cur, expr + "-" + chunk)  # minus
                backtrack(i + 1, total - last + last * cur,              # times
                          last * cur, expr + "*" + chunk)


    backtrack(0, 0, 0, "")
    return results




num = "123"
target = 6
print(add_operators(num, target))

The output of the above code will be:

['1+2+3', '1*2*3']

Let us read the Python version line by line and see why the running value works.

The function backtrack carries four things. The pos is where we are in the digit string. The total is the value of the expression so far. The last is the last operand, which is the most recent signed number folded into the total. The expr is the expression string we have built.

The line if pos == len(num) checks if we used every digit. We can only keep an expression when the whole string is used and the total equals the target.

The inner loop for i in range(pos, len(num)) tries every length of the next number. The line if i > pos and num[pos] == "0" breaks the loop when a multi-digit chunk would start with zero. So 0 alone is allowed but 05 is blocked.

The line if pos == 0 handles the very first number. It has no operator in front. So the total and the last operand both become that first number.

The plus branch sets the total to total + cur and the last operand to cur. The minus branch sets the total to total - cur and the last operand to -cur. The signed last operand matters for the next step.

The times branch is the clever one. The expression total - last + last * cur first removes the last operand from the total. Then it adds back last * cur. So if the last step added +2, and now we multiply by 3, we undo the +2 and add +6. The new last operand becomes last * cur, which is 6. This is exactly how times beats plus and minus in order without any parsing.

⏱️ Time and Space Complexity

At each gap between digits we have up to four choices, which are plus, minus, times, or gluing the digits. So the number of expressions grows like 4 to the power of n, where n is the number of digits. The running value lets us check each finished expression in constant time, so we never re-parse. The slow build-and-evaluate idea has the same branching but pays extra to parse every string again.

Approach Time Complexity Space Complexity
Build every string then evaluate O(4^n * n) O(n) recursion depth
Backtracking with running value O(4^n * n) O(n) recursion depth

Tip

The one line to remember is the times update. Take back the last operand, then fold the multiplication in. That single line gives you correct precedence with no parser at all.

🧩 Key Takeaways

  • ✅ Try plus, minus, times, or gluing digits at every gap between numbers.
  • ✅ Carry a running total so you never parse the expression again.
  • ✅ Keep the last operand so multiplication can undo and redo it for correct precedence.
  • ✅ Block multi-digit numbers that start with zero, like 05.
  • ✅ Save the expression only when the whole string is used and the total matches the target.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why must we keep the last operand during the recursion?

    Why: Times binds tighter than plus and minus, so we undo the last operand and fold the multiplication in.

  2. 2

    What does total - last + last * cur compute for the times branch?

    Why: It removes the last operand from the total and adds back last * cur, giving correct precedence.

  3. 3

    Why do we break the loop when a multi-digit chunk starts with zero?

    Why: A leading zero in a multi-digit number is invalid, so we stop building that chunk.

  4. 4

    When do we save an expression as a valid answer?

    Why: Only a fully built expression whose value equals the target counts as an answer.

Score: 0 / 4

🚀 What’s Next?

Previous Remove Invalid Parentheses Next Sudoku Solver