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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4
5

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

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

  1. Use backtracking to try every possible split of the string into numbers and every possible operator between them.
  2. 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
  3. For multiplication, subtract the previous operand from the current value, then add the result of multiplying the previous operand and the current number.
  4. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        dfs(result, num, target, "", 0, 0, 0);
        return result;
    }
    private void dfs(List<String> result, String num, int target, String expr, long calcVal, long preNum, int pos) {
        if (pos == num.length()) {
            if (calcVal == target) result.add(expr);
            return;
        }
        for (int i = pos; i < num.length(); i++) {
            if (i != pos && num.charAt(pos) == '0') break;
            long curNum = Long.parseLong(num.substring(pos, i + 1));
            if (pos == 0) {
                dfs(result, num, target, expr + curNum, curNum, curNum, i + 1);
            } else {
                dfs(result, num, target, expr + "+" + curNum, calcVal + curNum, curNum, i + 1);
                dfs(result, num, target, expr + "-" + curNum, calcVal - curNum, -curNum, i + 1);
                dfs(result, num, target, expr + "*" + curNum, calcVal - preNum + preNum * curNum, preNum * curNum, i + 1);
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        res = []
        def dfs(expr, calcVal, preNum, pos):
            if pos == len(num):
                if calcVal == target:
                    res.append(expr)
                return
            for i in range(pos, len(num)):
                if i != pos and num[pos] == '0':
                    break
                curNum = int(num[pos:i+1])
                if pos == 0:
                    dfs(str(curNum), curNum, curNum, i+1)
                else:
                    dfs(expr + '+' + str(curNum), calcVal + curNum, curNum, i+1)
                    dfs(expr + '-' + str(curNum), calcVal - curNum, -curNum, i+1)
                    dfs(expr + '*' + str(curNum), calcVal - preNum + preNum * curNum, preNum * curNum, i+1)
        dfs("", 0, 0, 0)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        dfs(res, num, target, "", 0, 0, 0);
        return res;
    }
private:
    void dfs(vector<string>& res, const string& num, int target, string expr, long calcVal, long preNum, int pos) {
        if (pos == num.size()) {
            if (calcVal == target) res.push_back(expr);
            return;
        }
        for (int i = pos; i < num.size(); ++i) {
            if (i != pos && num[pos] == '0') break;
            long curNum = stol(num.substr(pos, i - pos + 1));
            if (pos == 0) {
                dfs(res, num, target, expr + to_string(curNum), curNum, curNum, i + 1);
            } else {
                dfs(res, num, target, expr + "+" + to_string(curNum), calcVal + curNum, curNum, i + 1);
                dfs(res, num, target, expr + "-" + to_string(curNum), calcVal - curNum, -curNum, i + 1);
                dfs(res, num, target, expr + "*" + to_string(curNum), calcVal - preNum + preNum * curNum, preNum * curNum, i + 1);
            }
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func addOperators(num string, target int) []string {
    var res []string
    var dfs func(expr string, calcVal, preNum int64, pos int)
    dfs = func(expr string, calcVal, preNum int64, pos int) {
        if pos == len(num) {
            if calcVal == int64(target) {
                res = append(res, expr)
            }
            return
        }
        for i := pos; i < len(num); i++ {
            if i != pos && num[pos] == '0' {
                break
            }
            curNum, _ := strconv.ParseInt(num[pos:i+1], 10, 64)
            if pos == 0 {
                dfs(fmt.Sprintf("%d", curNum), curNum, curNum, i+1)
            } else {
                dfs(expr+"+"+fmt.Sprintf("%d", curNum), calcVal+curNum, curNum, i+1)
                dfs(expr+"-"+fmt.Sprintf("%d", curNum), calcVal-curNum, -curNum, i+1)
                dfs(expr+"*"+fmt.Sprintf("%d", curNum), calcVal-preNum+preNum*curNum, preNum*curNum, i+1)
            }
        }
    }
    dfs("", 0, 0, 0)
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun addOperators(num: String, target: Int): List<String> {
        val res = mutableListOf<String>()
        fun dfs(expr: String, calcVal: Long, preNum: Long, pos: Int) {
            if (pos == num.length) {
                if (calcVal == target.toLong()) res.add(expr)
                return
            }
            for (i in pos until num.length) {
                if (i != pos && num[pos] == '0') break
                val curNum = num.substring(pos, i + 1).toLong()
                if (pos == 0) {
                    dfs("$curNum", curNum, curNum, i + 1)
                } else {
                    dfs("$expr+$curNum", calcVal + curNum, curNum, i + 1)
                    dfs("$expr-$curNum", calcVal - curNum, -curNum, i + 1)
                    dfs("$expr*$curNum", calcVal - preNum + preNum * curNum, preNum * curNum, i + 1)
                }
            }
        }
        dfs("", 0, 0, 0)
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn add_operators(num: String, target: i32) -> Vec<String> {
        fn dfs(res: &mut Vec<String>, num: &str, target: i64, expr: String, calc_val: i64, pre_num: i64, pos: usize) {
            if pos == num.len() {
                if calc_val == target {
                    res.push(expr);
                }
                return;
            }
            for i in pos..num.len() {
                if i != pos && num.as_bytes()[pos] == b'0' {
                    break;
                }
                let cur_num = num[pos..=i].parse::<i64>().unwrap();
                if pos == 0 {
                    dfs(res, num, target, cur_num.to_string(), cur_num, cur_num, i + 1);
                } else {
                    dfs(res, num, target, format!("{}+{}", expr, cur_num), calc_val + cur_num, cur_num, i + 1);
                    dfs(res, num, target, format!("{}-{}", expr, cur_num), calc_val - cur_num, -cur_num, i + 1);
                    dfs(res, num, target, format!("{}*{}", expr, cur_num), calc_val - pre_num + pre_num * cur_num, pre_num * cur_num, i + 1);
                }
            }
        }
        let mut res = Vec::new();
        dfs(&mut res, &num, target as i64, String::new(), 0, 0, 0);
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    addOperators(num: string, target: number): string[] {
        const res: string[] = [];
        function dfs(expr: string, calcVal: number, preNum: number, pos: number) {
            if (pos === num.length) {
                if (calcVal === target) res.push(expr);
                return;
            }
            for (let i = pos; i < num.length; i++) {
                if (i !== pos && num[pos] === '0') break;
                const curNum = Number(num.slice(pos, i + 1));
                if (pos === 0) {
                    dfs(curNum.toString(), curNum, curNum, i + 1);
                } else {
                    dfs(expr + '+' + curNum, calcVal + curNum, curNum, i + 1);
                    dfs(expr + '-' + curNum, calcVal - curNum, -curNum, i + 1);
                    dfs(expr + '*' + curNum, calcVal - preNum + preNum * curNum, preNum * curNum, i + 1);
                }
            }
        }
        dfs("", 0, 0, 0);
        return res;
    }
}