AlgoViz
HomeBacktracking

Expression Add Operators

Hard

Insert an operator, carry the last term for *

Problem

Given a digit string and a target, insert +, -, * between digits so the expression evaluates to target; return all such expressions.

In simple words

Between digits try each operator, tracking the running value and the last term for multiply.

The idea

Walk the digit string choosing where to cut the next operand, then try +, - and * before it. Multiplication is the awkward one because it binds tighter than the running sum, so you carry the previous term along and undo it before re-applying: total - prev + prev * operand.

The trick

  • Track both the running total and the last term applied, or * will bind wrongly.
  • Skip any operand with a leading zero unless it is the single digit 0.
  • The first operand takes no operator — handle it as a separate base case.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

123
6
0
1

Step 1 of 2. Here's the example — num='123', target=6 Values: 123, 6.

1/2
Optimal
timeO(4^n)spaceO(n)
1dfs(pos, expr, value, prevOperand):2  if pos==n: if value==target output expr3  for each split of the next number:4    try +,-,* updating value (multiply uses prevOperand)

Input

array
[123, 6]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.