249. Expression Add Operators
Your function receives a string num made only of digits and an integer target. Between adjacent digits you may insert one of the binary operators +, -, or * — or nothing at all, which glues the digits into a longer number. The function must return every expression built this way whose value equals target, evaluated with the usual precedence (multiplication binds before addition and subtraction; there is no unary minus and no parentheses).
Two rules keep things honest:
- Operands may not have leading zeros:
"05"is not a valid number, though a lone"0"is fine. - Every digit of
nummust be used, in the original order.
Return the expressions sorted in lexicographic (ASCII) order — note that * < + < - < any digit in ASCII, which is why "1*2*3" lists before "1+2+3".
Example 1:
Input: num = "123", target = 6
Output: ["1*2*3", "1+2+3"]
Explanation: Both insertions evaluate to 6. In ASCII, '*' sorts before '+', so the product form comes first.
Example 2:
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Explanation: Precedence matters: 2*3+2 = 8 and 2+3*2 = 8, with each multiplication evaluated before the addition.
Example 3:
Input: num = "105", target = 5
Output: ["1*0+5", "10-5"]
Explanation: Gluing digits is allowed (10-5), but "1+05" is rejected because the operand 05 has a leading zero.
Constraints:
- 1 ≤ num.length ≤ 10
- num consists of digits only
- -2³¹ ≤ target ≤ 2³¹ - 1
- All intermediate values fit in a signed 64-bit integer.
Hints:
There are only three gaps' worth of choices per position: put +, -, * in a gap, or leave it empty to extend the current operand. With at most 9 gaps that is 4^9 combinations — small enough to enumerate, if each candidate can be checked quickly.
Evaluating with precedence in one left-to-right pass: keep a running total of finished terms plus the current product term. On '+' or '-' fold the term into the total and start a new (possibly negated) term; on '*' multiply into the term; add the final term at the end.
The backtracking refinement carries the evaluation into the recursion so nothing is re-parsed: track (position, total, last term). Appending '*v' replaces the last term t with t*v — update the value as total - t + t*v.
Prune leading zeros at generation time: when an operand starts with '0', it may only be the single digit "0" — stop extending it. Collect all hits and sort them at the end to meet the required output order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: num = "123", target = 6
Expected output: ["1*2*3", "1+2+3"]