Expression Add Operators: The Multiplication Precedence Trick

Problem Statement#

You are given a digit string num and an integer target. Insert any combination of binary operators +, -, * between digits to form arithmetic expressions that evaluate to target. Return all such expressions.

For num = "123" and target = 6, the answer is ["1+2+3", "1*2*3"]. For num = "232" and target = 8, the answer is ["2*3+2", "2+3*2"]. The classic gotcha: operands with leading zeros (like 05) are forbidden, and standard operator precedence applies, so multiplication must override the running sum.

Why This Problem Matters#

LeetCode 282 is a hard-tier interview favorite at Meta, Google, and Amazon for senior IC roles. It tests three things at once: enumerating combinations of digit splits and operators (a 4-way decision tree), correctly modeling operator precedence inside a recursive evaluator, and pruning leading-zero operands. Candidates who can write this clean in 25 minutes signal strong recursion fundamentals plus the rare ability to handle stateful expression evaluation without parsing into an AST.

The Core Insight (decision tree / state space)#

At each step of the recursion we are sitting at index idx and asking: "What is the next operand?" That operand can be 1, 2, or up to n - idx digits long. Once we pick the operand, we must decide which operator binds it to the running expression — +, -, or *. So at each gap between digits we have roughly 4 branches: pick a length, then pick one of three operators (the first operand has no operator).

The trick is multiplication precedence. When we choose *, we cannot just multiply into the accumulator, because the previous addition has already committed. Instead we maintain a last variable holding the value of the most recently added operand. To multiply, we undo that addition and redo it as a multiplication:

new_eval = eval - last + last * current
new_last = last * current

For + current we have new_eval = eval + current, new_last = current. For - current we have new_eval = eval - current, new_last = -current. The negative last is essential — if the next operator is *, we still want to multiply against the signed operand.

Visual Dry Run (recursion tree)#

For num = "232", target = 8:

                       bt(idx=0, path="", eval=0, last=0)
                      /         |          \
                pick "2"     pick "23"    pick "232"
                    |            ...         (leaf, eval=232 != 8)
              bt(1, "2", 2, 2)
              /        |        \
         +"3"        -"3"        *"3"
       bt(2,"2+3",   bt(2,"2-3", bt(2,"2*3",
          5, 3)        -1, -3)     6, 6)
        /  |  \      ...           /  |  \
      +2  -2  *2                 +2  -2  *2
   "2+3+2"  ...                "2*3+2"  ...
   eval=7                      eval=8 -> MATCH

The branch 2*3+2 evaluates to 8 because we computed eval=6, last=6 after the multiplication, then did eval = 6 + 2 = 8. The branch 2+3*2 works because at the * step we did eval = 5 - 3 + 3*2 = 8. That is the precedence trick in action.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

def addOperators(num, target):
    n, result = len(num), []
 
    def backtrack(idx, path, eval_val, last):
        if idx == n:
            if eval_val == target:
                result.append(path)
            return
        for i in range(idx, n):
            seg = num[idx:i + 1]
            if len(seg) > 1 and seg[0] == '0':
                break  # leading zero pruning
            val = int(seg)
            if idx == 0:
                backtrack(i + 1, seg, val, val)
            else:
                backtrack(i + 1, path + '+' + seg, eval_val + val, val)
                backtrack(i + 1, path + '-' + seg, eval_val - val, -val)
                backtrack(i + 1, path + '*' + seg,
                          eval_val - last + last * val, last * val)
 
    backtrack(0, '', 0, 0)
    return result

function addOperators(num, target) {
  const n = num.length;
  const result = [];
  const backtrack = (idx, path, evalVal, last) => {
    if (idx === n) {
      if (evalVal === target) result.push(path);
      return;
    }
    for (let i = idx; i < n; i++) {
      const seg = num.slice(idx, i + 1);
      if (seg.length > 1 && seg[0] === '0') break;
      const val = Number(seg);
      if (idx === 0) {
        backtrack(i + 1, seg, val, val);
      } else {
        backtrack(i + 1, path + '+' + seg, evalVal + val, val);
        backtrack(i + 1, path + '-' + seg, evalVal - val, -val);
        backtrack(i + 1, path + '*' + seg,
                  evalVal - last + last * val, last * val);
      }
    }
  };
  backtrack(0, '', 0, 0);
  return result;
}

Complexity: time is O(n times 4^n) — three operator choices per gap, n gaps, and string concatenation per call costs O(n). Space is O(n) recursion depth plus the output. For JavaScript, prefer BigInt if the digit string is long enough to overflow a 53-bit Number.

Common Mistakes#

• Forgetting the last variable and applying * directly to eval. This silently breaks 2+3*2 style cases.
• Allowing operands with leading zeros. Always break (not continue) once you detect seg[0] == '0' and len(seg) > 1 — a longer chunk with the same prefix is also invalid.
• Using int types in languages where intermediate products can overflow. Use long/long long/BigInt defensively.
• Making last unsigned. After a -, last must be negative so the next * multiplies the right sign.

Interview Tips#

• State the precedence trick out loud first — interviewers want to hear "I will track the last operand to undo and redo for multiplication."
• Mention the 4^n upper bound and explain why it is tight in adversarial inputs.
• Walk through "232" on the board; it is the smallest case that exercises both + and * paths.
• Discuss the leading-zero break as a pruning step, not an afterthought.

Follow-up Questions#

• Allow division. How does the trick change? (You need rationals, not just last.)
• What if you must use exactly k operators? Add a counter to the state.
• Return the count of valid expressions instead of the list — same recursion, drop the path string.
• Different Ways to Add Parentheses (LeetCode 241) — divide-and-conquer cousin.

Key Takeaways#

• The multiplication precedence trick — eval - last + last * val — is the heart of LeetCode 282.
• Backtracking enumerates operand splits and operator choices; the decision tree has roughly 4^n leaves.
• Leading-zero pruning uses break, not continue, because longer segments share the bad prefix.
• Carry the signed last across - operations so subsequent multiplications stay correct.
• This problem is a hard-tier interview staple at FAANG; mastering it unlocks calculator-style follow-ups.
• The same state-machine pattern (eval, last, path) generalizes to many expression-evaluation problems.

Sources:

• Expression Add Operators - LeetCode
• 282. Expression Add Operators - Detailed Explanation