DSA Factory
Free Backtracking lessonsBacktracking · Stage 4 · Mastery · Step 3

Insert operators to reach a target

Put plus, minus or times between the digits of a string, or nothing at all to join digits, to make an expression equal to a target, tracking the last term so that times is applied correctly. About 26 minutes.

Operand, then operator

The digits are fixed in order. At each step, choose how many digits form the next number: one, two or more. A number with a leading zero is not allowed unless it is just 0.

Between numbers you put plus, minus or times. The first number has no operator before it. Try the operand lengths from shortest to longest, and for each, the operators in the order plus, minus, times.

Operand: one or more digits, no leading zero.
Operator order: plus, then minus, then times.
In code
if j > i and num[i] == "0":
    break      # no number like 05
Reach the target 8 from the digits 2, 3, 2.
2
0
3
1
2
2
i

Start with the number 2. The value is 2, and the last term is 2.

Move 1 of 3

Times needs the last term

Times binds tighter than plus and minus. If the value so far is 2 plus 3 and the next operator is times 4, the new value is 2 plus 3 times 4, not 5 times 4. So remember the last term added to the value.

To apply times, remove the last term from the value and add the product of the last term and the new number instead. The new last term is that product. For minus, the last term is the new number with its sign changed.

Plus: value + n, last term n.
Times: value − last + last × n, last term last × n.
In code
value = value - last + last * n
Quick check

The value so far is 2 + 3 = 5 with last term 3, and the next number 4 comes with times. What is the new value?

  1. A14, since 2 + 3 × 4
  2. B20, since 5 × 4
  3. C9
Show the answer

14, since 2 + 3 × 4. 5 minus the last term 3, plus 3 times 4, is 14.

Your problem

Expression add operators

You are given a string num of digits and a number target. Put +, - or * between some of the digits (or nothing, to join digits into a longer number) so that the expression equals target, and return all such expressions. Numbers may not have leading zeros. List the expressions in the order a recursive search finds them: choose the first number's length from shortest to longest, then do the same for each next number, trying the operators in the order +, -, *.

Example
num = "123", target = 6 → ["1+2+3", "1*2*3"]

1 ≤ length of num ≤ 7 · -1,000,000 ≤ target ≤ 1,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve