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 Sam K., 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

More Recursion practice problems

See all Recursion problems →