We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Expression Add Operators

Difficulty: Hard

Problem Description

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value. Note that operands in the returned expressions should not contain leading zeros.

Key Insights

  • The problem requires generating all possible expressions by inserting operators between digits.
  • Backtracking is a suitable approach to explore all combinations of operator insertions.
  • Care must be taken to avoid leading zeros in multi-digit numbers.
  • The evaluation of expressions must be done considering operator precedence (multiplication before addition and subtraction).

Space and Time Complexity

Time Complexity: O(4^N) where N is the number of digits in the input string, as there are at most 3 operators to insert between N digits. Space Complexity: O(N) for the recursion stack during backtracking.

Solution

The solution involves a backtracking algorithm. The key steps are:

  1. Recursively build expressions by iterating through the string and inserting operators between digits.
  2. Evaluate the expression using a helper function that respects operator precedence.
  3. Check if the evaluated expression matches the target, adding valid expressions to the result list.
  4. Ensure no leading zeros in any operands during the construction of expressions.

Code Solutions

def addOperators(num: str, target: int):
    def backtrack(index: int, prev_operand: int, current_operand: int, value: int, expression: str):
        if index == len(num):
            if value == target and current_operand == 0:
                results.append(expression)
            return
        
        current_num = ""
        for i in range(index, len(num)):
            current_num += num[i]
            if len(current_num) > 1 and current_num[0] == '0':  # Skip leading zeros
                break
            
            current_operand = int(current_num)
            # Recur with '+'
            backtrack(i + 1, current_operand, 0, value + current_operand, expression + '+' + current_num if expression else current_num)
            # Recur with '-'
            backtrack(i + 1, -current_operand, 0, value - current_operand, expression + '-' + current_num if expression else current_num)
            # Recur with '*'
            backtrack(i + 1, prev_operand * current_operand, 0, value - prev_operand + (prev_operand * current_operand), expression + '*' + current_num if expression else current_num)

    results = []
    backtrack(0, 0, 0, 0, "")
    return results
← Back to All Questions