Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

282. Expression Add Operators - Leetcode Solution

Code Implementation

class Solution:
    def addOperators(self, num: str, target: int):
        res = []
        def dfs(index, path, value, prev):
            if index == len(num):
                if value == target:
                    res.append(path)
                return
            for i in range(index + 1, len(num) + 1):
                tmp = num[index:i]
                if len(tmp) > 1 and tmp[0] == '0':
                    break
                n = int(tmp)
                if index == 0:
                    dfs(i, tmp, n, n)
                else:
                    dfs(i, path + '+' + tmp, value + n, n)
                    dfs(i, path + '-' + tmp, value - n, -n)
                    dfs(i, path + '*' + tmp, value - prev + prev * n, prev * n)
        dfs(0, '', 0, 0)
        return res
      
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        function<void(int, string, long, long)> dfs = [&](int pos, string path, long value, long prev) {
            if (pos == num.size()) {
                if (value == target) res.push_back(path);
                return;
            }
            for (int i = pos + 1; i <= num.size(); ++i) {
                string tmp = num.substr(pos, i - pos);
                if (tmp.size() > 1 && tmp[0] == '0') break;
                long n = stol(tmp);
                if (pos == 0) {
                    dfs(i, tmp, n, n);
                } else {
                    dfs(i, path + "+" + tmp, value + n, n);
                    dfs(i, path + "-" + tmp, value - n, -n);
                    dfs(i, path + "*" + tmp, value - prev + prev * n, prev * n);
                }
            }
        };
        dfs(0, "", 0, 0);
        return res;
    }
};
      
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        dfs(num, target, 0, "", 0, 0, res);
        return res;
    }
    private void dfs(String num, int target, int pos, String path, long value, long prev, List<String> res) {
        if (pos == num.length()) {
            if (value == target) res.add(path);
            return;
        }
        for (int i = pos + 1; i <= num.length(); i++) {
            String tmp = num.substring(pos, i);
            if (tmp.length() > 1 && tmp.charAt(0) == '0') break;
            long n = Long.parseLong(tmp);
            if (pos == 0) {
                dfs(num, target, i, tmp, n, n, res);
            } else {
                dfs(num, target, i, path + "+" + tmp, value + n, n, res);
                dfs(num, target, i, path + "-" + tmp, value - n, -n, res);
                dfs(num, target, i, path + "*" + tmp, value - prev + prev * n, prev * n, res);
            }
        }
    }
}
      
var addOperators = function(num, target) {
    let res = [];
    function dfs(index, path, value, prev) {
        if (index === num.length) {
            if (value === target) res.push(path);
            return;
        }
        for (let i = index + 1; i <= num.length; i++) {
            let tmp = num.slice(index, i);
            if (tmp.length > 1 && tmp[0] === '0') break;
            let n = Number(tmp);
            if (index === 0) {
                dfs(i, tmp, n, n);
            } else {
                dfs(i, path + '+' + tmp, value + n, n);
                dfs(i, path + '-' + tmp, value - n, -n);
                dfs(i, path + '*' + tmp, value - prev + prev * n, prev * n);
            }
        }
    }
    dfs(0, '', 0, 0);
    return res;
};

Problem Description

You are given a string num consisting of only digits and an integer target. Your task is to add the binary operators '+', '-', or '*' between the digits in num (not necessarily between every digit) so that the resulting mathematical expression evaluates to target. Return all such possible expressions in any order.
  • Each digit in num must be used in the original order and exactly once.
  • You cannot reorder the digits or omit any of them.
  • You may not have numbers with leading zeros (except for the number '0' itself).
  • Operators can be inserted between any two digits, or not at all.
  • All valid expressions that evaluate to target should be returned.

Thought Process

At first glance, this problem seems to invite a brute-force approach: try every possible way of inserting the operators between the digits, evaluate each resulting expression, and collect those that match the target. However, brute-force evaluation can quickly become infeasible as the number of digits increases, since the number of possible combinations grows exponentially. A key insight is that we need to generate all valid expressions, but also evaluate them efficiently and correctly, especially given operator precedence (multiplication before addition and subtraction). To avoid redundant computation, we should build expressions incrementally and keep track of the running total, as well as the most recent operand (to handle multiplication precedence). We also need to handle leading zeros, ensuring we do not generate numbers like "05" or "00" as valid operands. Finally, recursion (backtracking) is a natural fit for this problem, as we can try each operator at each position, backtrack, and try the next possibility.

Solution Approach

To solve this problem efficiently, we use a recursive backtracking approach. Here’s how it works step-by-step:
  1. Recursive Function: Define a function that takes the current index in num, the expression built so far (path), the computed value so far (value), and the value of the last operand (prev).
  2. Base Case: If we've reached the end of the string, check if the computed value equals target. If so, add the current expression to the result list.
  3. Iterate Over Possible Splits: For each possible split of the remaining string (from current index to end), extract the substring and convert it to a number. Skip any number with leading zeros (except '0').
  4. First Number Special Case: For the very first operand, just recurse without adding any operator.
  5. Add Operators Recursively: For subsequent operands, recursively try adding '+', '-', and '*' before the new number:
    • For '+', add the number to the running total and recurse.
    • For '-', subtract the number from the running total and recurse.
    • For '*', carefully handle operator precedence: subtract the last operand from the total, multiply it with the new number, and add the result back (simulating parenthesis).
  6. Backtrack: After each recursive call, backtrack and try the next operator or split.
This approach ensures we generate all valid expressions without redundant computation, and correctly handle operator precedence.

Example Walkthrough

Let's walk through an example with num = "123" and target = 6.
  • Start with index 0, path "", value 0, prev 0.
  • First pick "1" (index 0 to 1):
    • Next, pick "2" (index 1 to 2):
      • Add '+': "1+2", value = 3, prev = 2
      • Pick "3" (index 2 to 3):
        • "1+2+3" = 6 (matches target) → add to result
        • "1+2-3" = 0
        • "1+2*3" = 7
      • Add '-': "1-2", value = -1, prev = -2
      • Pick "3":
        • "1-2+3" = 2
        • "1-2-3" = -4
        • "1-2*3" = -5
      • Add '*': "1*2", value = 2, prev = 2
      • Pick "3":
        • "1*2+3" = 5
        • "1*2-3" = -1
        • "1*2*3" = 6 (matches target) → add to result
    • Next, pick "23" (index 1 to 3):
      • "1+23" = 24
      • "1-23" = -22
      • "1*23" = 23
  • Next, pick "12" (index 0 to 2):
    • Pick "3" (index 2 to 3):
      • "12+3" = 15
      • "12-3" = 9
      • "12*3" = 36
  • Next, pick "123" (index 0 to 3):
    • "123" = 123
The final results are ["1+2+3", "1*2*3"].

Time and Space Complexity

  • Brute-force approach: For each digit, we can either insert an operator or not, leading to up to O(4^{n-1}) possible expressions for n digits (since there are 3 operators and the "no operator" choice). Evaluating each expression naively can take up to O(n) time.
  • Optimized recursive approach: We still explore all possible operator insertions, so the number of recursive calls is exponential in the worst case. However, by evaluating expressions as we build them (instead of parsing strings), we avoid redundant work and reduce overhead.
  • Space complexity: The recursion stack can be up to O(n) deep, and the result list can contain up to O(4^{n-1}) expressions in the worst case.

Summary

The "Expression Add Operators" problem is a classic example of using backtracking to generate all possible expressions while efficiently evaluating their results. The key insights are:
  • Build expressions recursively, trying all operator insertions.
  • Evaluate expressions as you build them to avoid costly string parsing.
  • Track the previous operand to handle multiplication precedence correctly.
  • Prune invalid numbers with leading zeros.
This approach is elegant because it combines recursion, backtracking, and careful state management to efficiently solve a combinatorial problem.