Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Expression Add Operators

HARDProblemSolveExternal Links

Description

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

Key rules:

  • You may insert operators between any two adjacent digits.
  • A number in the expression can span multiple consecutive digits (e.g., "123" can be treated as the number 123).
  • Numbers in the expressions must not have leading zeros ("05" is invalid, but "0" alone is valid).
  • Standard operator precedence applies: multiplication is performed before addition and subtraction.
  • Return the results in any order.

Examples

Example 1

Input: num = "123", target = 6

Output: ["1+2+3", "123"]

Explanation: Both "1+2+3" and "123" evaluate to 6. These are the only ways to insert operators into "123" to achieve the target.

Example 2

Input: num = "232", target = 8

Output: ["23+2", "2+32"]

Explanation: "23+2" = 6+2 = 8, and "2+32" = 2+6 = 8. Note that multiplication takes precedence over addition.

Example 3

Input: num = "3456237490", target = 9191

Output: []

Explanation: No combination of operators between the digits of "3456237490" can produce 9191.

Constraints

  • 1 <= num.length <= 10
  • num consists of only digits
  • -2^31 <= target <= 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward approach is to generate every possible expression by inserting operators between digits, and then evaluate each expression independently to check if it equals the target.

Think of the string as a sequence of characters with gaps between them. At each gap, we have a choice:

  1. Don't split — extend the current number by including the next digit (e.g., "1" becomes "12").
  2. Split with '+' — start a new number with addition.
  3. Split with '-' — start a new number with subtraction.
  4. Split with '*' — start a new number with multiplication.

This gives us up to 4 choices at each of the n−1 gaps, producing up to 4^(n−1) candidate expressions.

For each complete expression, we use a stack-based evaluator that respects operator precedence:

  • For '+' and '-': push the operand (positive or negative) onto the stack.
  • For '*': pop the top of the stack, multiply by the new operand, and push the result back.
  • At the end, sum the stack to get the final value.

If the value equals the target, the expression is a valid answer.

This approach is conceptually simple — separate the generation step from the evaluation step — but it's wasteful because we fully evaluate each expression from scratch at every leaf of the recursion tree, repeating work that could be done incrementally.

Step-by-Step Explanation

Let's trace the brute force approach on num = "123", target = 6.

Step 1: Start with an empty expression and index 0. Pick the first number from position 0 — it can be "1", "12", or "123".

Step 2: Choose "1". Now from index 1, we can pick "2" or "23" as the next number, preceded by an operator (+, -, or *). Try "+2".

Step 3: From index 2, pick "3" with operator. Try "+3". Expression is now "1+2+3". We've consumed all digits, so evaluate: push 1, encounter +2 push 2, encounter +3 push 3. Stack = [1, 2, 3]. Sum = 6. 6 == target ✓! Add to results.

Step 4: Backtrack. Try "-3" instead. Expression: "1+2-3". Evaluate: push 1, push 2, push -3. Sum = 0. 0 ≠ 6 ✗.

Step 5: Try "3". Expression: "1+23". Evaluate: push 1, encounter +2 push 2, encounter *3 pop 2, push 2×3=6. Stack = [1, 6]. Sum = 7. 7 ≠ 6 ✗.

Step 6: Backtrack further. Try "-2", "*2" from "1". With "2", then "3": expression "123". Evaluate: push 1, encounter *2 pop 1, push 1×2=2, encounter *3 pop 2, push 2×3=6. Stack = [6]. Sum = 6. 6 == target ✓!

Step 7: Continue exploring: "1+23" evaluates to 24 ✗, "1-23" to -22 ✗, "123" to 23 ✗, "12+3" to 15 ✗, "12-3" to 9 ✗, "123" to 36 ✗, "123" to 123 ✗. All fail.

Step 8: Result: ["1+2+3", "123"]. Every single expression was generated as a string and evaluated from scratch using the stack-based parser.

Brute Force — Generate All Expressions, Evaluate at Leaves — Watch how every possible expression is generated via backtracking, and each complete expression is evaluated from scratch at the leaf nodes.

Algorithm

  1. Define a recursive function generate(index, expr) that builds expressions character by character:
    a. Base case: If index equals the length of num, the expression is complete. Evaluate it using a stack-based parser. If the result equals target, add the expression to the answer list.
    b. For each ending position i from index to len(num) - 1:
    • Extract the substring num[index..i] as the next number.
    • Leading zero check: If the substring has more than one digit and starts with '0', break (no leading zeros allowed).
    • If index == 0 (first number in expression): recurse with just the number (no operator prefix).
    • Otherwise: recurse three times with the number preceded by '+', '-', and '*'.
  2. Define a stack-based evaluate(expr) function:
    • Scan the expression left to right. Accumulate digits into a number.
    • When encountering an operator or end of string:
      • If previous operator was '+': push the number.
      • If '-': push the negative of the number.
      • If '*': pop the top, multiply by the number, push result.
    • Return the sum of all values on the stack.
  3. Call generate(0, "") and return the collected results.

Code

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> result;
        generate(num, 0, "", result, target);
        return result;
    }

private:
    void generate(const string& num, int idx, const string& expr,
                  vector<string>& result, int target) {
        if (idx == (int)num.size()) {
            if (!expr.empty() && evaluate(expr) == target) {
                result.push_back(expr);
            }
            return;
        }
        for (int i = idx; i < (int)num.size(); i++) {
            if (i != idx && num[idx] == '0') break;
            string part = num.substr(idx, i - idx + 1);
            if (idx == 0) {
                generate(num, i + 1, part, result, target);
            } else {
                generate(num, i + 1, expr + "+" + part, result, target);
                generate(num, i + 1, expr + "-" + part, result, target);
                generate(num, i + 1, expr + "*" + part, result, target);
            }
        }
    }

    long long evaluate(const string& expr) {
        vector<long long> stk;
        long long num = 0;
        char sign = '+';
        for (int i = 0; i < (int)expr.size(); i++) {
            if (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
            }
            if (!isdigit(expr[i]) || i == (int)expr.size() - 1) {
                if (sign == '+') stk.push_back(num);
                else if (sign == '-') stk.push_back(-num);
                else if (sign == '*') stk.back() *= num;
                sign = expr[i];
                num = 0;
            }
        }
        long long res = 0;
        for (long long v : stk) res += v;
        return res;
    }
};
class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        result = []

        def evaluate(expr: str) -> int:
            stack = []
            n, sign = 0, '+'
            for i, ch in enumerate(expr):
                if ch.isdigit():
                    n = n * 10 + int(ch)
                if ch in '+-*' or i == len(expr) - 1:
                    if sign == '+':
                        stack.append(n)
                    elif sign == '-':
                        stack.append(-n)
                    elif sign == '*':
                        stack[-1] *= n
                    sign = ch
                    n = 0
            return sum(stack)

        def generate(idx: int, expr: str) -> None:
            if idx == len(num):
                if expr and evaluate(expr) == target:
                    result.append(expr)
                return
            for i in range(idx, len(num)):
                if i != idx and num[idx] == '0':
                    break
                part = num[idx:i + 1]
                if idx == 0:
                    generate(i + 1, part)
                else:
                    generate(i + 1, expr + '+' + part)
                    generate(i + 1, expr + '-' + part)
                    generate(i + 1, expr + '*' + part)

        generate(0, '')
        return result
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        generate(num, 0, "", result, target);
        return result;
    }

    private void generate(String num, int idx, String expr,
                          List<String> result, int target) {
        if (idx == num.length()) {
            if (!expr.isEmpty() && evaluate(expr) == target) {
                result.add(expr);
            }
            return;
        }
        for (int i = idx; i < num.length(); i++) {
            if (i != idx && num.charAt(idx) == '0') break;
            String part = num.substring(idx, i + 1);
            if (idx == 0) {
                generate(num, i + 1, part, result, target);
            } else {
                generate(num, i + 1, expr + "+" + part, result, target);
                generate(num, i + 1, expr + "-" + part, result, target);
                generate(num, i + 1, expr + "*" + part, result, target);
            }
        }
    }

    private long evaluate(String expr) {
        Deque<Long> stk = new ArrayDeque<>();
        long num = 0;
        char sign = '+';
        for (int i = 0; i < expr.length(); i++) {
            char ch = expr.charAt(i);
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            }
            if (!Character.isDigit(ch) || i == expr.length() - 1) {
                if (sign == '+') stk.push(num);
                else if (sign == '-') stk.push(-num);
                else if (sign == '*') stk.push(stk.pop() * num);
                sign = ch;
                num = 0;
            }
        }
        long res = 0;
        for (long v : stk) res += v;
        return res;
    }
}

Complexity Analysis

Time Complexity: O(n² × 4^n)

At each of the n−1 gaps between digits, we have 4 choices (3 operators or extend the current number), producing up to O(4^n) candidate expressions. Each complete expression at a leaf node has length O(n) and must be fully parsed and evaluated from scratch using the stack-based evaluator, costing O(n) per expression. String concatenation during generation also costs O(n) per recursive call. The combined cost is O(n² × 4^n).

Space Complexity: O(n)

The recursion depth is at most n (one level per digit). The expression string being built grows to at most O(n) characters. The evaluation stack holds at most O(n) values. Excluding the output list, auxiliary space is O(n).

Why This Approach Is Not Efficient

The fundamental problem with the brute force approach is the redundant evaluation at every leaf node. Each time we reach a complete expression, we parse the entire string from scratch and evaluate it using a stack — even though we had been incrementally building the expression the whole time.

Consider expression "1+2+3" and "1+2-3" and "1+2*3". All three share the prefix "1+2", which evaluates to 3. But in the brute force, we parse and evaluate "1+2" three separate times — once for each leaf. This redundancy multiplies across the entire tree.

What if we could maintain the running evaluation as we build the expression? Then at each node of the recursion tree, we already know the value of the expression so far. When we extend it with a new operator and number, we update the value in O(1) instead of re-evaluating the entire string in O(n).

The challenge is multiplication precedence. For '+' and '-', the update is trivial: just add or subtract the new number from the running total. But for '*', we can't simply multiply the running total — we need to know the last operand so we can undo its effect and apply multiplication correctly.

For example, if we have "2+3" with running total 5 and then multiply by 4:

  • Wrong: 5 × 4 = 20 (this computes (2+3)×4)
  • Right: 5 − 3 + 3×4 = 14 (this correctly computes 2 + 3×4)

By tracking a prev variable (the last operand, which was 3 in this case), we can "undo" the addition and apply multiplication with the correct precedence — all in O(1) time. This eliminates the need for any separate evaluation step entirely.

Optimal Approach - Backtracking with Inline Evaluation

Intuition

The optimal approach uses the same backtracking structure to explore all possible expressions, but it evaluates the expression incrementally during the recursion rather than at the end.

At each recursive call, we maintain two extra values:

  • curr — the current value of the expression built so far.
  • prev — the last operand that was added or subtracted. This is the key to handling multiplication correctly.

When we extend the expression with a new number next:

  • Addition (+): curr_new = curr + next, prev_new = next
  • Subtraction (-): curr_new = curr - next, prev_new = -next (We store -next because if a future multiplication needs to undo this subtraction, it needs to add back the negative value.)
  • Multiplication (×): This is the crucial case. We need to undo the effect of the last operand and replace it with the product:
    • curr_new = curr - prev + prev × next
    • prev_new = prev × next

The formula curr - prev + prev × next works because:

  1. curr - prev undoes the last addition/subtraction, restoring the expression value before the previous operand.
  2. prev × next applies multiplication with the correct precedence.
  3. Adding them gives the correct evaluation.

At the base case (all digits consumed), we simply check curr == target — no separate evaluation needed. This reduces the per-leaf cost from O(n) to O(1).

Step-by-Step Explanation

Let's trace the optimal approach on num = "123", target = 6, showing curr and prev at every step.

Step 1: Start: index=0, curr=0, prev=0. Choose "1" as the first number (no operator). Update: curr=1, prev=1.

Step 2: From index 1, try operator '+' with number 2. Update: curr = 1+2 = 3, prev = 2.

Step 3: From index 2, try operator '+' with number 3. Update: curr = 3+3 = 6, prev = 3. All digits consumed. Check: 6 == 6 ✓. Found "1+2+3"!

Step 4: Backtrack. Try operator '-' with number 3. curr = 3−3 = 0, prev = −3. Check: 0 ≠ 6 ✗.

Step 5: Try operator '*' with number 3. Apply the formula: curr = 3 − 2 + 2×3 = 3 − 2 + 6 = 7, prev = 2×3 = 6. Check: 7 ≠ 6 ✗. The formula correctly computes 1+(2×3) = 7, not (1+2)×3 = 9.

Step 6: Backtrack to "1". Try operator '-' with number 2: curr = 1−2 = −1, prev = −2. All three extensions from here fail (curr values: 2, −4, −5). Backtrack.

Step 7: Try operator '*' with number 2: curr = 1−1+1×2 = 2, prev = 1×2 = 2. The formula undoes the original placement of 1 and replaces it with 1×2.

Step 8: From "12", try '' with 3: curr = 2−2+2×3 = 6, prev = 2×3 = 6. Check: 6 == 6 ✓. Found "123"! The formula correctly computes 1×2×3 = 6.

Step 9: Explore remaining branches: "1+23" → curr=24, "123" → curr=23, "12+3" → curr=15, "123" → curr=36, "123" → curr=123. All ≠ 6.

Step 10: Result: ["1+2+3", "123"]. Every evaluation was O(1) — just arithmetic updates to curr and prev. No separate parsing or stack evaluation needed.

Optimal — Inline Evaluation with curr/prev Tracking — Watch how the expression value is maintained incrementally during recursion. The curr and prev variables enable O(1) evaluation at each step, with the multiplication formula 'curr - prev + prev × next' handling operator precedence correctly.

Algorithm

  1. Define a recursive function dfs(index, prev, curr, path) where:
    • index = current position in the string
    • prev = the last operand (needed for multiplication undoing)
    • curr = the current evaluation result of the expression
    • path = the expression string built so far
  2. Base case: If index == len(num), check if curr == target. If yes, add path to the result list.
  3. For each ending position i from index to len(num) - 1:
    • Extract next_num = int(num[index..i]).
    • Leading zero check: If the substring has multiple digits starting with '0', break.
    • First number (index == 0): No operator prefix. Recurse with dfs(i+1, next_num, next_num, str(next_num)).
    • Addition (+): dfs(i+1, next_num, curr + next_num, path + "+" + str(next_num))
    • Subtraction (-): dfs(i+1, -next_num, curr - next_num, path + "-" + str(next_num))
      Note: prev is stored as -next_num so that future multiplication correctly undoes the subtraction.
    • Multiplication (×): dfs(i+1, prev * next_num, curr - prev + prev * next_num, path + "*" + str(next_num))
      The formula curr - prev + prev * next_num undoes the last operand's effect and applies multiplication with correct precedence.
  4. Call dfs(0, 0, 0, "") and return the result list.

Code

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> result;
        dfs(num, target, 0, 0, 0, "", result);
        return result;
    }

private:
    void dfs(const string& num, int target, int index,
             long long prev, long long curr, const string& path,
             vector<string>& result) {
        if (index == (int)num.size()) {
            if (curr == target) {
                result.push_back(path);
            }
            return;
        }
        for (int i = index; i < (int)num.size(); i++) {
            if (i != index && num[index] == '0') break;
            string part = num.substr(index, i - index + 1);
            long long next = stoll(part);
            if (index == 0) {
                dfs(num, target, i + 1, next, next, part, result);
            } else {
                dfs(num, target, i + 1, next, curr + next,
                    path + "+" + part, result);
                dfs(num, target, i + 1, -next, curr - next,
                    path + "-" + part, result);
                dfs(num, target, i + 1, prev * next,
                    curr - prev + prev * next,
                    path + "*" + part, result);
            }
        }
    }
};
class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        result = []

        def dfs(index: int, prev: int, curr: int, path: str) -> None:
            if index == len(num):
                if curr == target:
                    result.append(path)
                return
            for i in range(index, len(num)):
                if i != index and num[index] == '0':
                    break
                part = num[index:i + 1]
                next_num = int(part)
                if index == 0:
                    dfs(i + 1, next_num, next_num, part)
                else:
                    dfs(i + 1, next_num, curr + next_num,
                        path + '+' + part)
                    dfs(i + 1, -next_num, curr - next_num,
                        path + '-' + part)
                    dfs(i + 1, prev * next_num,
                        curr - prev + prev * next_num,
                        path + '*' + part)

        dfs(0, 0, 0, '')
        return result
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        dfs(num, target, 0, 0, 0, "", result);
        return result;
    }

    private void dfs(String num, int target, int index,
                     long prev, long curr, String path,
                     List<String> result) {
        if (index == num.length()) {
            if (curr == target) {
                result.add(path);
            }
            return;
        }
        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == '0') break;
            String part = num.substring(index, i + 1);
            long next = Long.parseLong(part);
            if (index == 0) {
                dfs(num, target, i + 1, next, next, part, result);
            } else {
                dfs(num, target, i + 1, next, curr + next,
                    path + "+" + part, result);
                dfs(num, target, i + 1, -next, curr - next,
                    path + "-" + part, result);
                dfs(num, target, i + 1, prev * next,
                    curr - prev + prev * next,
                    path + "*" + part, result);
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n × 3^n)

At each position in the string, we branch into at most 3 recursive calls (one for each operator: +, -, *). Additionally, we try different substring lengths for multi-digit numbers. The total number of recursive paths is bounded by O(3^n) where n is the length of the string. Each path involves O(n) work for string concatenation (building the expression path), giving O(n × 3^n) overall. The inline evaluation with curr/prev is O(1) per call, which is a significant improvement over the O(n) per-leaf evaluation in the brute force.

Space Complexity: O(n)

The recursion depth is at most n (one level per character in the worst case). Each stack frame stores constant-sized variables (index, prev, curr). The expression path string has length at most O(n). Excluding the output list, the auxiliary space is O(n).