LeetCode 282: Expression Add Operators Solution in Python – A Step-by-Step Guide

What Is LeetCode 282: Expression Add Operators?

In LeetCode 282: Expression Add Operators, you’re given a string num containing only digits (0-9) and an integer target. Your task is to insert the operators +, -, or * between the digits to form expressions that evaluate to target, returning all valid expressions as a list. For example, with num = "123" and target = 6, valid answers include ["1+2+3", "123"]. The catch? You can’t change the order of digits, must use all of them, and need to handle tricky cases like leading zeros or operator precedence (multiplication before addition/subtraction). This problem blends recursion and math, echoing challenges like LeetCode 241: Different Ways to Add Parentheses.

Problem Statement

• Input: A string num (digits only) and an integer target.
• Output: A list of strings—valid expressions that evaluate to target.
• Rules: Use +, -, *; no parentheses; all digits in order; no leading zeros in multi-digit numbers.

Constraints

• num length: 1 to 10.
• num: digits 0-9, no leading zeros in input.
• target: -10⁹ to 10⁹.

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"]
• Input: num = "105", target = 5
• Output: ["1*0+5", "10-5"]

Understanding the Problem: Crafting the Expression

To solve LeetCode 282: Expression Add Operators in Python, we need to explore every way to split num into numbers and operators that equal target. For "123" and 6, we could have single digits (1+2+3) or combine them (12+3-9 doesn’t work, but 123 does). Brute-forcing all possibilities is slow, so we’ll use: 1. Best Solution (Backtracking with DFS): O(4ⁿ) time—smart and manageable. 2. Alternative Solution (String Building): O(4ⁿ) time—simpler but less optimized.

Let’s dive into the DFS solution with a beginner-friendly walkthrough.

Best Solution: Backtracking with DFS

Why This Is the Best Solution

The backtracking DFS approach is the star for LeetCode 282 because it’s efficient for this exponential problem—O(4ⁿ) time (where n is the string length)—and uses O(n) space for recursion. It evaluates expressions on the fly, avoiding unnecessary string copies, and handles multiplication precedence naturally. For beginners, it’s like exploring a maze, trying paths, and backtracking when they don’t work—super powerful once you get the hang of it!

How It Works

Picture this as building an expression step-by-step: you pick a chunk of digits, decide how to use it (+, -, *), compute the result so far, and keep going until you’ve used all digits—checking if you hit the target. Here’s the breakdown, explained simply:

• Step 1: Define the DFS Function:
• Parameters: current position in num, current value, previous operand (for *), the growing expression, and the result list.
• Base case: If at the end of num, check if current value equals target.

• Step 2: Explore Options:
• At each position, take a substring (e.g., "1", "12", "123").
• For each substring:
• Add it (+).
• Subtract it (-).
• Multiply it with the previous operand (*), adjusting the current value.
• No operator (concatenate to prior number, e.g., 1 → 12).

• Step 3: Handle Multiplication:
• Track the previous operand separately—undo its addition, then multiply and re-add.
• E.g., for 1+2*3, after 1+2=3, adjust to 1+(2*3)=7.

• Step 4: Avoid Leading Zeros:
• Skip multi-digit numbers starting with 0 (e.g., "05" is invalid).

• Step 5: Collect Results:
• When num is fully used and value matches target, add the expression.

It’s like trying every fork in the road until you find the treasure!

Step-by-Step Example

Example: num = "123", target = 6

• Start: pos=0, val=0, prev=0, expr="".
• pos=0: Take "1":
• DFS(pos=1, val=1, prev=1, expr="1"):
• Take "2":
• +: DFS(pos=2, val=3, prev=2, "1+2"):
• "3": +: val=6, expr="1+2+3" → match!
• *: DFS(pos=2, val=1+(2*1)=3, prev=2, "1*2"):
• "3": *: val=1+(2*3)=7, "1*2*3" → no match, but try +: val=6, "1*2*3" → match!
• Result: ["1+2+3", "1*2*3"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result = []

        def dfs(pos: int, val: int, prev: int, expr: str):
            # Base case: end of string
            if pos == len(num):
                if val == target:
                    result.append(expr)
                return

            # Try all substrings from current position
            curr = 0
            for i in range(pos, len(num)):
                curr = curr * 10 + int(num[i])  # Build number
                curr_str = num[pos:i+1]

                # Skip if leading zero in multi-digit
                if len(curr_str) > 1 and curr_str[0] == '0':
                    break

                # First number: no operator before
                if pos == 0:
                    dfs(i + 1, curr, curr, curr_str)
                else:
                    # Add
                    dfs(i + 1, val + curr, curr, expr + "+" + curr_str)
                    # Subtract
                    dfs(i + 1, val - curr, -curr, expr + "-" + curr_str)
                    # Multiply
                    dfs(i + 1, val - prev + prev * curr, prev * curr, expr + "*" + curr_str)

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

• Line 4: List to store valid expressions.
• Line 6-9: Base case: If at end, check if val matches target, add expr if so.
• Line 12-15: Build current number digit-by-digit (e.g., "12" = 1*10 + 2).
• Line 17-19: Skip invalid multi-digit numbers with leading zeros.
• Line 21-22: First number—no operator, just use it.
• Line 24-28: For later numbers:
• +: Add curr to val.
• -: Subtract curr from val.
• *: Undo prev addition (val - prev), then add prev * curr.
• Line 30: Start DFS from beginning.

• Time Complexity: O(4ⁿ)—at each digit, choose +, -, *, or none.
• Space Complexity: O(n)—recursion depth.

This is like a math adventure—try, adjust, succeed!

Alternative Solution: String Building with Backtracking

Why an Alternative Approach?

Building the string first then evaluating it is more intuitive—O(4ⁿ) time still—but requires an extra evaluation step, making it less efficient. It’s like writing down all recipes before tasting them—great for understanding the flow.

How It Works

• Step 1: Use DFS to build expressions with operators.
• Step 2: Evaluate each complete expression (using eval or custom parser).
• Step 3: Collect those matching target.

Step-by-Step Example

num = "123", target = 6

• Build: "1+2+3" → eval = 6 → add.
• Build: "1*2*3" → eval = 6 → add.
• Result: ["1+2+3", "1*2*3"].

Code for String Building

Copy codeclass Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        result = []

        def dfs(pos: int, expr: str):
            if pos == len(num):
                if eval(expr) == target:
                    result.append(expr)
                return
            curr = num[pos]
            if pos == 0:
                dfs(pos + 1, curr)
            else:
                for op in ['+', '-', '*']:
                    dfs(pos + 1, expr + op + curr)
            if num[pos] != '0':
                dfs(pos + 1, expr + curr)

        dfs(0, "")
        return [x for x in result if not (len(x) > 1 and x[0] == '0' and x[1].isdigit())]

• Time Complexity: O(4ⁿ)—plus evaluation overhead.
• Space Complexity: O(n)—recursion and strings.

It’s simpler but slower due to eval.

Comparing the Two Solutions

• DFS (Best):
• Pros: O(4ⁿ) time, computes on-the-fly, no eval.
• Cons: Tricky with multiplication.
• String Building (Alternative):
• Pros: Easier to follow, builds first.
• Cons: Eval step adds cost, less efficient.

DFS wins for performance.

Additional Examples and Edge Cases

• "00", target=0: ["0+0", "0-0", "0*0"].
• "5", target=5: ["5"].
• "100", target=100: ["100"].

Both handle these well.

Complexity Breakdown

• DFS: Time O(4ⁿ), Space O(n).
• String: Time O(4ⁿ) + eval, Space O(n).

DFS is the champ.

Key Takeaways

• DFS: Compute as you go—smart!
• String: Build then check—clear but slow.
• Backtracking: Explore all paths.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Operate Like a Pro

LeetCode 282: Expression Add Operators in Python is a brain-teasing math puzzle. DFS keeps it fast and sharp, while string-building offers a gentler start. Want more? Try LeetCode 241: Different Ways to Add Parentheses or LeetCode 227: Basic Calculator II. Ready to calculate? Head to Solve LeetCode 282 on LeetCode and add those operators today!