HardNeetCode150MathStringBacktracking
Expression Add Operators
Add +, -, * between digits to reach target.
Examples
Input
num = "123", target = 6
Output
['1+2+3','1*2*3']
Two expressions reaching 6.
Constraints
- •
1 <= num.length <= 10 - •
-2^31 <= target <= 2^31-1 - •
num does not contain leading zeros
Approaches
Try all operator placements.
CodeT: O(4^n) | S: O(n) recursion depth
Handle * by tracking prev operand.
CodeT: O(4^n) | S: O(n)
Same approach.
CodeT: O(4^n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Backtracking | O(4^n) | O(n) recursion depth | Try all operator placements. |
| Backtracking + Track Product | O(4^n) | O(n) | Handle * by tracking prev operand. |
| Backtracking Optimized | O(4^n) | O(n) | Same approach. |
Backtracking
T: O(4^n)S: O(n) recursion depth
Try all operator placements.
Backtracking + Track Product
T: O(4^n)S: O(n)
Handle * by tracking prev operand.
Backtracking Optimized
T: O(4^n)S: O(n)
Same approach.
Common Mistakes
Not handling multiplication precedence
Leading zeros
Off-by-one