Operators Between Digits
HardBacktracking
Problem
You are given a string of digits num and an integer target. Between any two adjacent digits you may insert +, -, *, or nothing (which glues the digits into a longer number).
Return every resulting expression that evaluates to target under normal precedence (* before + and -). Numbers in an expression may not have leading zeros: 0 is fine, 05 is not. Return the expressions in any order.
Example 1
- Input:
- num = "123", target = 6
- Output:
- ["1+2+3", "1*2*3"]
Both evaluate to 6; for example 12-3 = 9 does not.
Example 2
- Input:
- num = "105", target = 5
- Output:
- ["1*0+5", "10-5"]
"1*05" would need the number 05, which has a leading zero.
Constraints
- 1 ≤ num.length ≤ 10
- num contains only digits.
- -2^31 ≤ target ≤ 2^31 - 1
Hint
Show the first hint
Recurse over the position where the next number starts; try every length for that number, then every operator before it.
Walkthrough
How to approach it
01Clarify before coding
- Is gluing digits allowed? Yes, '10-5' uses '10'.
- Are leading zeros allowed? Only a lone '0'.
- Is unary minus allowed before the first number? No, operators go only between digits.
- Could intermediate values overflow 32 bits? Yes: 10 digits can form 9,999,999,999, so use 64-bit or big integers.
02Brute force
Generate all 4^(n-1) operator strings, build each expression, and evaluate it with a parser (or eval).
Cost: O(n · 4^(n-1)): about 262,144 expressions for n = 10, each re-parsed from scratch. It works, but re-evaluation is wasteful and eval is rarely accepted in an interview.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.