LeetCode Solutions Blog

Expression Add Operators

Number: 282

Difficulty: Hard

Paid? No

Problem Description

Given a string of digits and an integer target, insert the binary operators '+', '-', and/or '*' between the digits to form valid mathematical expressions that evaluate to the target value. Note that operands in the expressions should not have leading zeros unless the operand itself is zero.

Key Insights

Use backtracking/DFS to explore every possible way to split the string into numbers.
Handle operator precedence for '*' by tracking the last operand.
Check and avoid number segments with leading zeros.
The state in recursion should include the current expression string, the evaluated value so far, and the last operand used (to handle multiplication).

Space and Time Complexity

Time Complexity: O(4^n) in the worst-case, since at each digit we may choose different splits and operators. Space Complexity: O(n) for the recursion call stack and current expression storage.

Solution

We adopt a recursive backtracking solution that iterates over potential partitions of the string into numbers. When considering an operator insertion:

At the start, we simply take the number without adding an operator.
Otherwise, for each operator, update:
- For '+': add the new number to the evaluated result.
- For '-': subtract the new number.
- For '*': remove the effect of the last operand and add the product of the last operand with the new number.
Ensure that we do not form numbers with leading zeros.
When reaching the end of the string, check if the evaluated result equals the target. This approach leverages recursion with backtracking to try every valid possibility while correctly handling operator precedence using the last operand.

Code Solutions

# Define the main function that returns a list of valid expressions.
def addOperators(num, target):
    results = []
    
    # Helper function for backtracking.
    # index: current index in num
    # path: expression string built so far
    # evaluated: current evaluation of the expression
    # last: the last operand, used for multiplication adjustment
    def backtrack(index, path, evaluated, last):
        # If we reached the end of the string, check if the current evaluation equals target.
        if index == len(num):
            if evaluated == target:
                results.append(path)
            return
        
        # Try all possible splits starting from the current index.
        for i in range(index, len(num)):
            # Avoid numbers with leading zero.
            if i != index and num[index] == '0':
                break
            current_str = num[index:i+1]
            current_num = int(current_str)
            
            # If at the beginning of expression, don't add any operator.
            if index == 0:
                backtrack(i+1, current_str, current_num, current_num)
            else:
                # Addition
                backtrack(i+1, path + '+' + current_str, evaluated + current_num, current_num)
                # Subtraction
                backtrack(i+1, path + '-' + current_str, evaluated - current_num, -current_num)
                # Multiplication: adjust evaluated by removing last and adding the multiplication result.
                backtrack(i+1, path + '*' + current_str, evaluated - last + last * current_num, last * current_num)
    
    backtrack(0, "", 0, 0)
    return results

# For testing purposes
if __name__ == "__main__":
    print(addOperators("123", 6))  # Expected output: ["1+2+3", "1*2*3"]