282. Expression Add Operators - Detailed Explanation

Problem Statement

You are given a string num that contains only digits and an integer target. Your task is to return all valid expressions (as strings) that can be built by inserting the binary operators '+', '-', or '*' between the digits in num so that the resulting expression evaluates to the target value. Note that the digits must remain in their original order and you cannot insert any extra characters or change the order of the digits.

Important Points:

• Operands: Formed by combining consecutive digits.

• No Leading Zeros: Operands cannot have extra leading zeros (except the number zero itself).

• Operator Precedence: The multiplication operator (*) takes precedence over addition (+) and subtraction (-).

Example 1

• Input:

  num = "123"
  target = 6
  

• Output:

  ["1+2+3", "1*2*3"]
  

• Explanation:
  Both expressions evaluate to 6:
  • 1+2+3 = 6
  • 1*2*3 = 6

Example 2

• Input:

  num = "232"
  target = 8
  

• Output:

  ["2*3+2", "2+3*2"]
  

• Explanation:
  Both expressions evaluate to 8:
  • 2*3+2 = 6+2 = 8
  • 2+3*2 = 2+6 = 8

Example 3

• Input:

  num = "105"
  target = 5
  

• Output:

  ["1*0+5", "10-5"]
  

• Explanation:
  • 1*0+5 = 0+5 = 5
  • 10-5 = 5
    Note that "1*05" is not allowed because the operand "05" has a leading zero.

Constraints

• 1 <= num.length <= 10
• num consists of only digits.
• -2³¹ <= target <= 2³¹ - 1

Hints for the Approach

• Hint 1: Use backtracking (or DFS) to try every possible way to split the string into numbers and insert operators between them. This means at each step, decide the length of the current number and then try all three operators (or no operator at the very beginning).

• Hint 2: Think about handling the multiplication operator carefully. Since multiplication has a higher precedence than addition and subtraction, maintain an extra variable (e.g., tail or multed) that keeps track of the last operand so you can correctly update the current evaluation when a multiplication is encountered.

Approach 1: Brute Force Generation and Evaluation

Idea

• Generate All Expressions:
  Iterate over all possible ways to split the input string and insert operators. For every possible expression, evaluate it and check if it equals the target.

• Evaluation:
  Use a helper function to parse and evaluate the generated string expression.

Drawbacks

• Efficiency:
  Generating and evaluating every possible expression without pruning will be extremely inefficient, especially when the string length grows, because the number of possibilities grows exponentially.

• Operator Precedence:
  Handling the multiplication operator correctly (considering operator precedence) makes evaluation tricky.

Approach 2: Backtracking with Recursive DFS (Optimal)

Idea

Instead of generating all expressions first, use a recursive backtracking approach to build the expression on the fly while keeping track of the current evaluation. For each recursive call, decide:

• Partition:
  How many digits to take from the current index to form the next operand.

• Operators:
  If it’s not the first operand, choose to insert '+', '-', or '*' before the operand.

• Tracking Values:
  Maintain three values:

  • expr: The current expression string.
  • calc: The current calculated value of the expression.
  • tail: The value of the last operand (used to handle multiplication).

Handling Multiplication

• When adding '+' or '-', update calc normally.
• For '*', subtract the last operand (tail) from calc and add the result of tail * current_number to handle the multiplication precedence

Pseudocode Overview

function backtrack(index, expr, calc, tail):
    if index == length of num:
        if calc == target:
            add expr to result list
        return

    for i from index to length of num:
        if number formed has leading zero (and length > 1): break
        current = num[index...i]
        if index == 0:
            backtrack(i+1, current, current, current)
        else:
            backtrack(i+1, expr + "+" + current, calc + current, current)
            backtrack(i+1, expr + "-" + current, calc - current, -current)
            backtrack(i+1, expr + "*" + current, calc - tail + tail * current, tail * current)

Detailed Explanation of the DFS Approach

Step-by-Step Walkthrough

1. Initialization:
   Start from index 0 with an empty expression string, a calculated value of 0, and no tail value.

2. Recursive Decision Making:
   For every recursive call:

   • Choose the next number by iterating from the current index to the end of the string.
   • Skip numbers with leading zeros (if the chosen number has more than one digit and starts with '0').

3. Handling the First Number:
   If it is the first number (i.e., index is 0), add it to the expression without any operator. Set both calc and tail to this number.

4. Adding Operators:
   For subsequent numbers, try all three possible operators:

   • Addition (+):
     Update calc as calc + current and set tail to current.
   • Subtraction (-):
     Update calc as calc - current and set tail to -current.
   • Multiplication (*):
     Since multiplication has a higher precedence, update calc as calc - tail + (tail * current) and update tail to tail * current.

5. Base Case:
   When the index reaches the end of num, check if the computed calc equals target. If so, add the expression to the result list.

Visual Example

Consider num = "123" and target = 6:

• First Call:
  • Choose "1" (index 0 to 0), set expr = "1", calc = 1, tail = 1.
• Second Call (index = 1):
  • Choose "2" (index 1 to 1) and try:
    • "1+2": calc = 1 + 2 = 3, tail = 2
    • "1-2": calc = 1 - 2 = -1, tail = -2
    • "1*2": calc = 1 - 1 + (1*2) = 2, tail = 2
• Third Call (index = 2):
  For each branch from above, choose "3":
  • From "1+2":
    • "1+2+3": calc = 3 + 3 = 6
    • "1+2-3": calc = 3 - 3 = 0
    • "1+2*3": calc = 3 - 2 + (2*3) = 7
  • From "1*2":
    • "1*2+3": calc = 2 + 3 = 5
    • "1*2-3": calc = 2 - 3 = -1
    • "1*2*3": calc = 2 - 2 + (2*3) = 6
• Result:
  The valid expressions are "1+2+3" and "1*2*3".

Python Implementation