04. Expression Add Operators

Difficulty:HardPattern:Combinatorial BacktrackingTime:O(4^N)Space:O(N)

Given a string num containing only digits and an integer target, return all possibilities to insert binary operators '+', '-', or '*' between the digits so that the resulting expression evaluates to target.

How It Works & Algorithmic Design

Solves using Operator Choice Backtracking with Multiplication Precedence Tracking:

DFS Signature: dfs(index, path, eval, multed).
Branch Choice: Extract substring currStr = num[index...i] with numeric value curr.
- Skip leading zero multi-digit strings (e.g. '05').
Operations:
- Start position (index === 0): dfs(i + 1, currStr, curr, curr).
- Addition +: dfs(i + 1, path + '+' + currStr, eval + curr, curr).
- Subtraction -: dfs(i + 1, path + '-' + currStr, eval - curr, -curr).
- Multiplication *: Undo last term addition then add product: dfs(i + 1, path + '*' + currStr, eval - multed + multed * curr, multed * curr).

Why This Approach Works Best

Tracking multed handles operator precedence naturally during left-to-right recursion.

Example Walkthrough

Input: num = "123", target = 6

Evaluate expression options.

Matches: "1+2+3" = 6 and "1*2*3" = 6.

Valid generated strings.

Output: ["1+2+3", "1*2*3"]

All valid operators.

Answer: Expression Add Operators implementation

function addOperators(num, target) {
  const res = [];
  function dfs(index, path, evalVal, multed) {
    if (index === num.length) {
      if (evalVal === target) res.push(path);
      return;
    }
    for (let i = index; i < num.length; i++) {
      if (i !== index && num[index] === '0') break;
      const str = num.substring(index, i + 1);
      const curr = Number(str);
      if (index === 0) {
        dfs(i + 1, str, curr, curr);
      } else {
        dfs(i + 1, path + '+' + str, evalVal + curr, curr);
        dfs(i + 1, path + '-' + str, evalVal - curr, -curr);
        dfs(i + 1, path + '*' + str, evalVal - multed + multed * curr, multed * curr);
      }
    }
  }
  dfs(0, '', 0, 0);
  return res;
}

💡 Recursively split digits into terms, testing plus, minus, and times operator additions.

Key Takeaways

Prune numbers with leading zeroes (e.g. '05').
Subtract multed from running evaluation before adding product term.
Explores $O(4^N)$ search paths.