Course4all
Join us on telegram
Home/dsa/Stack/Expression Add Operators

Expression Add Operators

Master this topic with zero to advance depth.

Expression Add Operators

Precedence and Multiplication

Adding + and - is straightforward: just add or subtract the current value. However, multiplication (*) has higher precedence. If we have 1 + 2 * 3, we cannot simply compute (1 + 2) * 3.

The Trick: Tracking Previous Operand

To handle prev + current * next, we need to subtract current and add current * next. Formula: NewTotal = (OldTotal - prevOperand) + (prevOperand * currentValue).

Corner Cases

  1. Leading Zeros: A number like "05" is invalid unless it's just "0".
  2. Overflow: Since the target and intermediate values can exceed 231−12^{31}-1, use long (64-bit integers).

Given a string num containing 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.

Hard

Examples

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Approach 1

Level I: Basic Backtracking with Post-Evaluation

Intuition

Insert every possible operator between digits to generate all possible expressions, then evaluate each one.

Generate expressions by recursion. For each string of length NN, there are 4N−14^{N-1} combinations. This is very slow due to the evaluation step.

⏱ O(N * 4^N)💾 O(N)

Detailed Dry Run

num="12", target=3.

  • Try "1+2" -> eval(3) == 3 -> SUCCESS.
  • Try "1-2" -> eval(-1) != 3.
  • Try "1*2" -> eval(2) != 3.
java
class Solution {
    // Naive version: generate all and evaluate.
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        backtrack(num, target, 1, "" + num.charAt(0), res);
        return res;
    }
    private void backtrack(String num, int target, int i, String expr, List<String> res) {
        if (i == num.length()) {
            if (evaluate(expr) == target) res.add(expr);
            return;
        }
        backtrack(num, target, i + 1, expr + "+" + num.charAt(i), res);
        backtrack(num, target, i + 1, expr + "-" + num.charAt(i), res);
        backtrack(num, target, i + 1, expr + "*" + num.charAt(i), res);
        backtrack(num, target, i + 1, expr + num.charAt(i), res);
    }
    private long evaluate(String s) { /* Standard expression eval */ return 0; }
}
Approach 2

Level II: Optimized Backtracking (Running Value)

Intuition

Calculate the expression value on the fly to avoid explicit evaluation. Handle multiplication by tracking the previous added value.

Use dfs(index, path, currentVal, prevOperand). If we add *, the new value is (currentVal - prevOperand) + (prevOperand * now).

⏱ O(4^N)💾 O(N)

Detailed Dry Run

num="123", target=6

  1. Pick "1": val=1, prev=1.
  2. Pick "2" with "+": val=1+2=3, prev=2.
  3. Pick "3" with "+": val=3+3=6, prev=3. SUCCESS.
  4. Pick "2" with "": val=(1-1)+(12)=2, prev=2.
  5. Pick "3" with "": val=(2-2)+(23)=6, prev=6. SUCCESS.
java
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        if (num == null || num.length() == 0) return res;
        dfs(0, "", 0, 0, num, target, res);
        return res;
    }
    private void dfs(int idx, String path, long val, long prev, String num, int target, List<String> res) {
        if (idx == num.length()) {
            if (val == target) res.add(path);
            return;
        }
        for (int i = idx; i < num.length(); i++) {
            if (i > idx && num.charAt(idx) == '0') break;
            String s = num.substring(idx, i + 1);
            long now = Long.parseLong(s);
            if (idx == 0) {
                dfs(i + 1, s, now, now, num, target, res);
            } else {
                dfs(i + 1, path + "+" + s, val + now, now, num, target, res);
                dfs(i + 1, path + "-" + s, val - now, -now, num, target, res);
                dfs(i + 1, path + "*" + s, val - prev + prev * now, prev * now, num, target, res);
            }
        }
    }
}
Approach 3

Level III: Memory-Optimized Backtracking

Intuition

Instead of building string paths and then converting them, use a char[] or byte[] to build the path directly, avoiding string concatenations which are expensive.

Pass a char[] (or byte[] in Go) to the recursive function. When adding an operator or digit, update the array and its current length. Backtrack by resetting the length.

⏱ O(4^N)💾 O(N)

Detailed Dry Run

num="123", target=6

  • path=['1'], len=1. dfs(1, 1, 1, path)
  • path=['1','+','2'], len=3. dfs(2, 3, 2, path)
  • path=['1','+','2','+','3'], len=5. dfs(3, 6, 3, path). Target hit. Add "1+2+3" to res.
  • Backtrack: path=['1','+','2'], len=3. Try '*'.
  • path=['1','+','2','','3'], len=5. dfs(3, 1+2-2+23=7, 2*3=6, path). Target not hit.
java
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        if (num == null || num.length() == 0) return res;
        char[] path = new char[num.length() * 2];
        dfs(res, path, 0, num.toCharArray(), 0, 0, 0, target);
        return res;
    }
    private void dfs(List<String> res, char[] path, int len, char[] num, int idx, long val, long prev, int target) {
        if (idx == num.length) {
            if (val == target) res.add(new String(path, 0, len));
            return;
        }
        long now = 0;
        int pos = len;
        if (idx != 0) len++;
        for (int i = idx; i < num.length; i++) {
            if (i > idx && num[idx] == '0') break;
            now = now * 10 + (num[i] - '0');
            path[len++] = num[i];
            if (idx == 0) {
                dfs(res, path, len, num, i + 1, now, now, target);
            } else {
                path[pos] = '+'; dfs(res, path, len, num, i + 1, val + now, now, target);
                path[pos] = '-'; dfs(res, path, len, num, i + 1, val - now, -now, target);
                path[pos] = '*'; dfs(res, path, len, num, i + 1, val - prev + prev * now, prev * now, target);
            }
        }
    }
}
← Previous QuestionBasic Calculator III
Next Question →Implement Trie (Prefix Tree)