hardBacktrackingPure DSA~50 min
Insert Operators To Hit A Target Value
Given a string of digits, insert the binary operators +, -, and * between them (concatenating digits is allowed for multi-digit numbers) to form arithmetic expressions. Return every expression that evaluates to a target value.
Problem
Given a string num of digits and an integer target, return all expressions formed by inserting +, -, * between the digits so the expression evaluates to target. Operands may not have leading zeros (except the single digit 0). Standard operator precedence applies (* before + and -).
Input
A digit string num and an integer target.
Output
A list of valid expression strings (any order).
Constraints
- 1 ≤ |num| ≤ 10
- num consists of digits only.
- -2^31 ≤ target ≤ 2^31 - 1
Examples
Example 1
Input
num="123" target=6
Output
["1*2*3","1+2+3"]
Both evaluate to 6.
Example 2
Input
num="105" target=5
Output
["1*0+5","10-5"]
Leading-zero operands like '05' are disallowed.