Skip to main content

282. Expression Add Operators

hard

Insert '+', '-', or '*' between digits of a string so the resulting expression evaluates to a target. Backtracking with one subtle requirement — multiplication's higher precedence forces you to track the 'last operand' along with the running total.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value. Note that operands in the returned expressions should not contain leading zeros.

Constraints

  • 1 <= num.length <= 10
  • num consists of only digits.
  • -2^31 <= target <= 2^31 - 1

Examples

Example 1

Input
num = "123", target = 6
Output
["1*2*3","1+2+3"]

Example 2

Input
num = "232", target = 8
Output
["2*3+2","2+3*2"]

Example 3

Input
num = "3456237490", target = 9191
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with (index, currentExpr, currentValue, lastOperand).

Hint 2

lastOperand matters because '*' modifies the previous operand: total - lastOperand + lastOperand * newOperand.

Hint 3

Try every prefix as the next operand (length 1..n - index). Skip if length > 1 and first char is '0' (no leading zeros).

Hint 4

Special-case the first operand — no leading operator. After that try '+', '-', '*' each.

Solution approach

Reveal approach

Backtrack with (index, expression-so-far, currentTotal, lastOperand). At index, loop end from index + 1 to n inclusive; let operand = num.substring(index, end); skip if operand.length > 1 and operand starts with '0' (no leading zeros). Let operandVal = parseInt(operand). If index == 0, recurse with expression = operand, currentTotal = operandVal, lastOperand = operandVal. Otherwise try three operators: '+' -> recurse with currentTotal + operandVal, lastOperand = operandVal; '-' -> recurse with currentTotal - operandVal, lastOperand = -operandVal; '*' -> recurse with currentTotal - lastOperand + lastOperand * operandVal, lastOperand = lastOperand * operandVal. When index == n, if currentTotal == target, append expression. The 'last operand' trick is what gives multiplication the right precedence — we undo the last addition before applying the multiplication.

Complexity

Time
O(n * 4^n)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • expression-evaluation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Google
  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Expression Add Operators and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →