LeetCode 282: Expression Add Operators – Recursive DFS for All Valid Math Expressions

Programming & Development / April 10, 2025

LeetCode 282: Expression Add Operators – Recursive DFS for All Valid Math Expressions

LeetCode 282 Expression Add Operators backtracking depth-first search arithmetic expression evaluation Python recursion operator insertion string to expression target expression sum

Copy Link Bookmark Print

Introduction

LeetCode 282: Expression Add Operators challenges you to insert +, -, and * operators between digits of a string to create expressions that evaluate to a given target value.

This problem is an elegant blend of:

String parsing
Backtracking
Expression evaluation (especially operator precedence)

Problem Statement

Given a string num that contains only digits and an integer target, return all valid expressions that can be built by inserting binary operators +, -, and * between the digits so that the resulting expression evaluates to the target.

You cannot reorder digits. Numbers in the expression can't have leading zeros (e.g., "05" is invalid).

Example

python

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

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

Input: num = "105", target = 5
Output: ["1*0+5", "10-5"]

✅ Step-by-Step Solution

🔍 Step 1: Think Recursively

We'll use DFS (depth-first search) to explore all combinations.

At each step:

Split the string into left (current number) and right (remaining digits)
Try inserting +, -, or *
Track:
The current expression (path)
Current evaluated result (value)
Last operand (needed for * to handle precedence correctly)

🔢 Step 2: Handling Multiplication

Because * has higher precedence, we can’t just evaluate left-to-right.

Example:

For expression "1+2*3", we need to evaluate 2*3 first
So we track the last number used and undo it if * is used:
value = value - last + (last * current)

⛔ Step 3: Prune Invalid States

No leading zeros: if a number starts with '0' and is longer than 1 digit, skip it.

✅ Python Code

python

class Solution:
    def addOperators(self, num: str, target: int) -> list[str]:
        result = []

        def dfs(index, path, value, last):
            if index == len(num):
                if value == target:
                    result.append(path)
                return

            for i in range(index + 1, len(num) + 1):
                curr_str = num[index:i]
                if len(curr_str) > 1 and curr_str[0] == '0':
                    break
                curr = int(curr_str)

                if index == 0:
                    dfs(i, curr_str, curr, curr)
                else:
                    dfs(i, path + '+' + curr_str, value + curr, curr)
                    dfs(i, path + '-' + curr_str, value - curr, -curr)
                    dfs(i, path + '*' + curr_str, value - last + last * curr, last * curr)

        dfs(0, "", 0, 0)
        return result

🧪 Dry Run (num = "123", target = 6)

Try: "1+2+3" → 6 ✅
Try: "123" → 6 ✅
Try: "1+23" → 24 ❌
Try: "12+3" → 15 ❌
Final result: ["1+2+3", "1*2*3"]

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(4^n) in worst caseSpace ComplexityO(n) recursion stack

🔍 Edge Cases

num = "000", target = 0 → many valid combos: "0+0+0", "0*0*0", etc.
Long input with invalid splits due to leading zeros

✅ Conclusion

LeetCode 282: Expression Add Operators is a great blend of recursion, parsing, and precedence handling. It teaches:

NUHMAN.com