s","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:T2a31,

Problem

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Note that a number can contain multiple digits.

Examples

Example 1:

Input:
num = "123", target = 6
Output:
 ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input:
num = "232", target = 8
Output:
 ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input:
num = "3456237490", target = 9191
Output:
 []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Example 4:

Input:
num = "3136", target = 8
Output:
 ["6*(3+1)/3"]
Explanation: `6 * (3 + 1) / 3 = 8`

Solution

Method 1 - Backtracking

Intuition

We want to insert '+', '-', and '*' between digits to form valid expressions that evaluate to the target. The main challenge is handling multiplication due to operator precedence. We use backtracking to try all possible splits and operator insertions, tracking the current value and the previous operand to correctly compute multiplication.

Approach

Use backtracking to try every possible split of the string into numbers and every possible operator between them.
For each recursive call, keep track of:
- The current expression string
- The current calculated value
- The previous operand (for multiplication)
- The current position in the string
For multiplication, subtract the previous operand from the current value, then add the result of multiplying the previous operand and the current number.
Avoid numbers with leading zeros except for '0' itself.

Complexity

⏰ Time complexity: O(4^n) — Each position can branch into up to 4 choices (split, +, -, *), but pruning for leading zeros and position 0 reduces this.
🧺 Space complexity: O(n) — The recursion stack and temporary expression string.

Code

[{"language":"Java","code":"class Solution {\n    public List<String> addOperators(String num, int target) {\n        List<String> result = new ArrayList<>();\n        dfs(result, num, target, \"\", 0, 0, 0);\n        return result;\n    }\n    private void dfs(List<String> result, String num, int target, String expr, long calcVal, long

Related Tags