Expression Add Operators

▶

Steps

setup

Start Backtracking at index 0

The algorithm begins at the start of the string with an empty expression path and zero evaluated value. It prepares to parse operands starting from index 0.

💡 Initializing the recursion sets the stage for exploring all possible expressions from the beginning of the input.

Line:

backtrack(0, 0, 0)

💡 The recursion starts with no expression and zero evaluation, ready to build expressions from the first digit.

fill_cells

Parse operand '1' at index 0-0 and add as first operand

The algorithm parses the substring '1' as the first operand. Since this is the first operand, it is added to the path without an operator.

💡 The first operand sets the base of the expression; no operator is needed before it.

Line:

curr_str = num[0:1]  # '1'
path.append(curr_str)
backtrack(1, 1, 1)

💡 The first operand initializes the expression and evaluation to 1.

fill_cells

Parse operand '2' at index 1-1 and add with '+' operator

From index 1, the substring '2' is parsed as the next operand. The '+' operator is appended before it, and the expression evaluation is updated accordingly.

💡 Adding '+' extends the expression and updates the evaluation by adding the new operand.

Line:

path.append('+'); path.append('2')
backtrack(2, 3, 2)

💡 The expression now is '1+2' with evaluation 3.

fill_cells

Parse operand '3' at index 2-2 and add with '+' operator

At index 2, the substring '3' is parsed as the next operand. The '+' operator is appended before it, updating the expression and evaluation.

💡 Adding '+' again extends the expression and updates evaluation by adding the operand.

Line:

path.append('+'); path.append('3')
backtrack(3, 6, 3)

💡 The expression '1+2+3' evaluates to 6, matching the target.

compare

Check if expression '1+2+3' matches target

Since the entire string is consumed (index == len(num)), the algorithm checks if the evaluated value equals the target.

💡 This is the base case where a complete expression is evaluated for validity.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 The expression '1+2+3' is a valid solution and is recorded.

backtrack

Backtrack to index 2 and try '-' operator with operand '3'

After exploring '+3', the algorithm backtracks to index 2 and tries the '-' operator before operand '3'.

💡 Backtracking allows exploring alternative operator choices at the same position.

Line:

path.append('-'); path.append('3')
backtrack(3, 0, -3)

💡 The expression '1+2-3' evaluates to 0, which is not the target.

compare

Check if expression '1+2-3' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '1+2-3' is invalid and will not be added to results.

backtrack

Backtrack to index 2 and try '*' operator with operand '3'

After exploring '-' operator, the algorithm tries '*' operator before operand '3'. It updates evaluation considering operator precedence.

💡 Multiplication requires adjusting the evaluated value by removing last operand and adding multiplied result.

Line:

path.append('*'); path.append('3')
backtrack(3, 1 + 2 * 3, 2 * 3)

💡 Expression '1+2*3' evaluates to 7, not the target.

compare

Check if expression '1+2*3' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '1+2*3' is invalid and will not be added to results.

backtrack

Backtrack to index 1 and try operand '23' with '+' operator

Backtracking to index 1, the algorithm parses '23' as the next operand and tries '+' operator before it.

💡 Parsing longer operands explores different splits of the input string.

Line:

curr_str = num[1:3]  # '23'
path.append('+'); path.append('23')
backtrack(3, 24, 23)

💡 Expression '1+23' evaluates to 24, not the target.

compare

Check if expression '1+23' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '1+23' is invalid and will not be added to results.

backtrack

Backtrack to index 0 and try operand '12' as first operand

Backtracking to the root, the algorithm parses '12' as the first operand and starts a new expression path.

💡 Trying longer first operands explores different expression bases.

Line:

curr_str = num[0:2]  # '12'
path.append('12')
backtrack(2, 12, 12)

💡 Expression starts with '12' and evaluation 12.

fill_cells

Parse operand '3' at index 2-2 and add with '+' operator

From index 2, the substring '3' is parsed as the next operand. The '+' operator is appended before it, updating the expression and evaluation.

💡 Adding '+' extends the expression and updates evaluation by adding the operand.

Line:

path.append('+'); path.append('3')
backtrack(3, 15, 3)

💡 Expression '12+3' evaluates to 15, not the target.

compare

Check if expression '12+3' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '12+3' is invalid and will not be added to results.

backtrack

Backtrack to index 0 and try operand '123' as first operand

Backtracking to the root, the algorithm parses '123' as the first operand and starts a new expression path.

💡 Trying the longest possible first operand explores all splits.

Line:

curr_str = num[0:3]  # '123'
path.append('123')
backtrack(3, 123, 123)

💡 Expression starts with '123' and evaluation 123.

compare

Check if expression '123' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '123' is invalid and will not be added to results.

backtrack

Backtrack to index 0 and try operand '1' with '-' operator

Backtracking to the root, the algorithm tries operand '1' as first operand, then explores '-' operator with next operands.

💡 Exploring all operators after the first operand is essential to find all valid expressions.

Line:

path.append('1')
backtrack(1, 1, 1)
path.append('-'); path.append('2')
backtrack(2, -1, -2)

💡 Expression '1-2' evaluates to -1, not the target.

fill_cells

Parse operand '3' at index 2-2 and add with '*' operator

From index 2, the substring '3' is parsed as the next operand. The '*' operator is appended before it, updating the expression and evaluation with precedence.

💡 Multiplication changes evaluation by combining with last operand.

Line:

path.append('*'); path.append('3')
backtrack(3, -1 - (-2) + (-2) * 3, -6)

💡 Expression '1-2*3' evaluates to -5, not the target.

compare

Check if expression '1-2*3' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '1-2*3' is invalid and will not be added to results.

backtrack

Backtrack to index 1 and try operand '2' with '*' operator and then operand '3'

Backtracking to index 1, the algorithm tries operand '2' with '*' operator and then operand '3' with '*' operator, forming '1*2*3'.

💡 Exploring multiplication chains is key to finding all valid expressions.

Line:

path.append('*'); path.append('2')
backtrack(2, 2, 2)
path.append('*'); path.append('3')
backtrack(3, 6, 6)

💡 Expression '1*2*3' evaluates to 6, matching the target.

compare

Check if expression '1*2*3' matches target

At the end of the string, the algorithm checks if the evaluated value equals the target.

💡 Only expressions matching the target are recorded as answers.

Line:

if index == len(num):
  if evaluated == target:
    res.append(''.join(path))

💡 Expression '1*2*3' is a valid solution and is recorded.

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):  # STEP 5, 7, 9, 11, 14, 16, 19, 21
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            if i != index and num[index] == '0':
                break
            curr_str = num[index:i+1]  # STEP 2, 10, 12, 15
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)  # STEP 2, 12, 15
                backtrack(i+1, curr, curr)  # STEP 2, 12, 15
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)  # STEP 3, 4, 10, 13
                backtrack(i+1, evaluated + curr, curr)  # STEP 3, 4, 10, 13
                path[length_before:] = []

                path.append('-'); path.append(curr_str)  # STEP 6, 17
                backtrack(i+1, evaluated - curr, -curr)  # STEP 6, 17
                path[length_before:] = []

                path.append('*'); path.append(curr_str)  # STEP 8, 18, 20
                backtrack(i+1, evaluated - last_operand + last_operand * curr, last_operand * curr)  # STEP 8, 18, 20
                path[length_before:] = []
    backtrack(0, 0, 0)  # STEP 1
    return res

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

📊

Expression Add Operators - Watch the Algorithm Execute, Step by Step

Watching this visualization helps you understand how backtracking incrementally builds expressions, prunes invalid paths, and collects valid answers without generating all permutations blindly.

enteringindex=0evaluated=0last_operand=0

Call Path (current → root)

backtrack(0,0,0)

Remaining

parse operand from index 0 to 0parse operand from index 0 to 1parse operand from index 0 to 2

enteringindex=1evaluated=1last_operand=1

Call Path (current → root)

backtrack(1,1,1)

backtrack(0,0,0)

Remaining

parse operand from index 1 to 1parse operand from index 1 to 2

Partial: [1]

enteringindex=2evaluated=3last_operand=2

Call Path (current → root)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Remaining

parse operand from index 2 to 2

Partial: [1, +, 2]

enteringindex=3evaluated=6last_operand=3

Call Path (current → root)

backtrack(3,6,3)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 2, +, 3]

backtrackingindex=3evaluated=6last_operand=3

Call Path (current → root)

backtrack(3,6,3)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 2, +, 3]

Found 1: [1+2+3]

enteringindex=3evaluated=0last_operand=-3

Call Path (current → root)

backtrack(3,0,-3)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 2, -, 3]

Found 1: [1+2+3]

backtrackingindex=3evaluated=0last_operand=-3

Call Path (current → root)

backtrack(3,0,-3)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 2, -, 3]

Found 1: [1+2+3]

enteringindex=3evaluated=7last_operand=6

Call Path (current → root)

backtrack(3,7,6)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 2, *, 3]

Found 1: [1+2+3]

backtrackingindex=3evaluated=7last_operand=6

Call Path (current → root)

backtrack(3,7,6)

backtrack(2,3,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 2, *, 3]

Found 1: [1+2+3]

enteringindex=3evaluated=24last_operand=23

Call Path (current → root)

backtrack(3,24,23)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 23]

Found 1: [1+2+3]

backtrackingindex=3evaluated=24last_operand=23

Call Path (current → root)

backtrack(3,24,23)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, +, 23]

Found 1: [1+2+3]

enteringindex=2evaluated=12last_operand=12

Call Path (current → root)

backtrack(2,12,12)

backtrack(0,0,0)

Remaining

parse operand from index 2 to 2

Partial: [12]

Found 1: [1+2+3]

enteringindex=3evaluated=15last_operand=3

Call Path (current → root)

backtrack(3,15,3)

backtrack(2,12,12)

backtrack(0,0,0)

Partial: [12, +, 3]

Found 1: [1+2+3]

backtrackingindex=3evaluated=15last_operand=3

Call Path (current → root)

backtrack(3,15,3)

backtrack(2,12,12)

backtrack(0,0,0)

Partial: [12, +, 3]

Found 1: [1+2+3]

enteringindex=3evaluated=123last_operand=123

Call Path (current → root)

backtrack(3,123,123)

backtrack(0,0,0)

Partial: [123]

Found 1: [1+2+3]

backtrackingindex=3evaluated=123last_operand=123

Call Path (current → root)

backtrack(3,123,123)

backtrack(0,0,0)

Partial: [123]

Found 1: [1+2+3]

enteringindex=2evaluated=-1last_operand=-2

Call Path (current → root)

backtrack(2,-1,-2)

backtrack(1,1,1)

backtrack(0,0,0)

Remaining

parse operand from index 2 to 2

Partial: [1, -, 2]

Found 1: [1+2+3]

enteringindex=3evaluated=-5last_operand=-6

Call Path (current → root)

backtrack(3,-5,-6)

backtrack(2,-1,-2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, -, 2, *, 3]

Found 1: [1+2+3]

backtrackingindex=3evaluated=-5last_operand=-6

Call Path (current → root)

backtrack(3,-5,-6)

backtrack(2,-1,-2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, -, 2, *, 3]

Found 1: [1+2+3]

enteringindex=3evaluated=6last_operand=6

Call Path (current → root)

backtrack(3,6,6)

backtrack(2,2,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, *, 2, *, 3]

Found 1: [1+2+3]

backtrackingindex=3evaluated=6last_operand=6

Call Path (current → root)

backtrack(3,6,6)

backtrack(2,2,2)

backtrack(1,1,1)

backtrack(0,0,0)

Partial: [1, *, 2, *, 3]

Found 2: [1+2+3] [1*2*3]

Key Takeaways

✓ Backtracking incrementally builds expressions by choosing operands and operators step-by-step, allowing efficient exploration of all valid expressions.

This insight is hard to see from code alone because the recursion and backtracking logic is intertwined and subtle.

✓ Handling multiplication requires careful evaluation updates to respect operator precedence, by adjusting the evaluated value using the last operand.

Understanding this adjustment is crucial and often confusing without seeing the evaluation state change visually.

✓ Backtracking prunes invalid paths early, such as skipping operands with leading zeros, which prevents unnecessary recursion and improves efficiency.

This pruning is subtle in code but becomes clear when watching the recursion tree skip certain branches.

Practice

1. Consider the following Python function implementing space-optimized bottom-up DP for edit distance. What is the value of current[1] after the first iteration of the inner loop when calling minDistance("abc", "ac") during the iteration where i = 2?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Identify iteration i=2 corresponds to last character 'c' in "abc"

   At i=2, word1[i] = 'c'. The inner loop runs j=1 to 0 for word2="ac".

2. Step 2: Compute current[1] when j=1 (word2[1] = 'c')

   Since word1[2] == word2[1] ('c' == 'c'), current[1] = next_row[2]. Initially, next_row = [2,1,0], so next_row[2] = 0.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matching chars yield current[j] = next_row[j+1] = 0 [OK]

Hint: Matching chars copy diagonal DP value [OK]

Common Mistakes:

• Off-by-one indexing in j or i
• Confusing current and next_row arrays

2. Consider the following Python code implementing the optimal solution for the envelope nesting problem. Given the input [[5,4],[6,4],[6,7],[2,3]], what is the value of the tails list after processing all heights?

easy

A. [3, 4, 7]

B. [3, 4]

C. [2, 3, 4, 7]

D. [2, 3, 7]

Solution

1. Step 1: Sort envelopes and extract heights

   Sorted envelopes: [[2,3],[5,4],[6,7],[6,4]] -> heights = [3,4,7,4]

2. Step 2: Trace tails updates

   Insert 3 -> tails=[3]; Insert 4 -> tails=[3,4]; Insert 7 -> tails=[3,4,7]; Insert 4 replaces tails[1] -> tails=[3,4,7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final tails length is 3 with values [3,4,7] [OK]

Hint: Trace tails updates carefully with bisect_left [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Not replacing tails element on equal height
• Misordering envelopes before LIS

3. The following code snippet is a near-correct implementation of the Trie-based palindrome pairs solution. Which line contains a subtle bug that causes incorrect results on inputs containing empty strings?

medium

A. Line missing palindrome_suffixes append after setting node.index

B. Line checking is_palindrome(word[:len(word)-i]) inside add_word loop

C. Line checking is_palindrome(word[i:]) inside search loop

D. Line returning res when ch not in node.children

Solution

1. Step 1: Identify missing palindrome suffix append

   After setting node.index, the code must append index to palindrome_suffixes to handle empty string cases correctly.

2. Step 2: Understand impact on empty string pairs

   Without this append, pairs involving empty strings and palindromic words are missed, causing incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding palindrome_suffixes append fixes empty string pairing [OK]

Hint: Empty string pairs require palindrome_suffixes append at word end [OK]

Common Mistakes:

• Forgetting to append palindrome_suffixes at word end
• Misplacing palindrome checks
• Incorrect early returns in search

4. Suppose you want to find the median of two sorted arrays where elements can be repeated infinitely (i.e., arrays represent multisets with unlimited duplicates). Which modification to the optimal binary search partition approach is necessary to handle this scenario correctly?

hard

A. Modify the partition condition to handle infinite duplicates by counting occurrences explicitly.

B. No modification needed; the existing binary search partition approach works as is.

C. Switch to a two-pointer partial merge approach to handle duplicates efficiently.

D. Use a frequency map and binary search on value range instead of indices.

Solution

1. Step 1: Understand infinite duplicates impact

   Infinite duplicates mean the arrays represent multisets with repeated elements beyond fixed length, so index-based partitioning is insufficient.

2. Step 2: Modify partition condition

   The binary search partition must be adapted to count occurrences and handle duplicates explicitly to find correct median position.

3. Step 3: Why other options fail

   No modification ignores duplicates; two-pointer merge loses logarithmic efficiency; frequency map changes problem nature.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Handling infinite duplicates requires counting occurrences in partition [OK]

Hint: Infinite duplicates require counting occurrences in partition [OK]

Common Mistakes:

• Assuming no change needed for duplicates
• Switching to merge loses optimal time
• Using frequency map changes problem scope

5. Suppose the problem is modified so that words can be reused multiple times in pairs (i.e., pairs (i, j) where i == j are allowed). Which modification to the Trie-based solution correctly handles this variant without double counting pairs?

hard

A. Remove the check 'node.index != index' and filter duplicates from final results

B. Keep the check 'node.index != index' but add a separate check for empty string pairs

C. Modify add_word to store multiple indices per node to allow reuse tracking

D. Remove the check 'node.index != index' in search to allow i == j pairs

Solution

1. Step 1: Understand reuse allowance

   Allowing i == j pairs means removing the 'node.index != index' check to include self-pairs.

2. Step 2: Avoid double counting

   Removing the check causes duplicates; filtering duplicates after collecting results ensures correctness.

3. Step 3: Evaluate other options

   Keeping the check disallows self-pairs; storing multiple indices per node is unnecessary and complex.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing check plus duplicate filtering correctly handles reuse [OK]

Hint: Allow self-pairs by removing check, then deduplicate results [OK]

Common Mistakes:

• Removing check without deduplication
• Keeping check and missing self-pairs
• Overcomplicating Trie nodes