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. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?

easy

A. Backtracking that explores all substring partitions and checks palindrome validity dynamically

B. Dynamic programming that counts the number of palindromic substrings without generating partitions

C. Greedy approach that picks the longest palindrome substring at each step

D. Breadth-first search that generates partitions level by level without palindrome checks

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all palindrome partitions, not just counting or finding one.

2. Step 2: Identify suitable algorithm

   Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with palindrome checks finds all partitions [OK]

Hint: Backtracking explores all partitions with palindrome pruning [OK]

Common Mistakes:

• Assuming greedy longest palindrome picks all partitions
• Confusing counting palindromes with generating partitions
• Ignoring palindrome checks in BFS

2. You are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?

easy

A. Use dynamic programming to store subproblems of partial word matches.

B. Use a greedy search that picks the next letter with the highest frequency in the grid.

C. Use backtracking combined with a Trie data structure to prune invalid prefixes early.

D. Search each word independently using DFS without any prefix pruning.

Solution

1. Step 1: Understand problem constraints

   The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.

2. Step 2: Identify efficient pruning technique

   Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie pruning reduces search space drastically compared to naive DFS [OK]

Hint: Trie + backtracking prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking greedy or DP alone can solve adjacency constraints efficiently.

3. What is the time complexity of generating all permutations of an array of length n using Heap's algorithm, and why might a common misconception about this complexity be incorrect?

medium

A. O(n! * n^2) because each permutation requires n swaps and there are n! permutations

B. O(n! * log n) because Heap's algorithm uses a heap data structure internally

C. O(n! * n) because each of the n! permutations requires copying the array of length n

D. O(n! + n) because generating permutations is factorial plus linear overhead

Solution

1. Step 1: Identify number of permutations

   There are n! permutations for an array of length n.

2. Step 2: Analyze cost per permutation

   Heap's algorithm generates each permutation with O(1) swaps, but copying the current permutation to the result list takes O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time complexity is O(n! * n) due to copying each permutation [OK]

Hint: Copying each permutation costs O(n), not the swaps themselves [OK]

Common Mistakes:

• Assuming swaps cost O(n) each or confusing heap data structure usage

4. Suppose the Sudoku solver is modified so that digits can be reused multiple times in the same row, column, or box (i.e., constraints are relaxed). Which of the following statements about the backtracking algorithm is true?

hard

A. Constraint checks can be removed, and backtracking reduces to brute force filling

B. Heuristic ordering of empty cells becomes unnecessary since constraints are relaxed

C. The existing backtracking with constraint propagation still works correctly without changes

D. The problem becomes trivial and can be solved in linear time by filling all empty cells with '1'

Solution

1. Step 1: Understand effect of relaxing constraints

   Allowing repeated digits removes Sudoku constraints, so no need to check row, column, or box validity.

2. Step 2: Impact on backtracking algorithm

   Backtracking degenerates to brute force filling since any digit can be placed anywhere; constraint propagation is useless.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Relaxed constraints mean no pruning, so backtracking is brute force [OK]

Hint: Relaxed constraints remove pruning, reverting to brute force [OK]

Common Mistakes:

• Assuming heuristics still help
• Thinking problem becomes trivial linear time

5. Suppose the Word Search problem is modified so that the same cell can be used multiple times in forming the word. Which modification to the backtracking algorithm correctly handles this change?

hard

A. Add a global visited set to track cells used in all paths

B. Keep marking visited cells but reset them after each recursion

C. Remove the in-place marking of visited cells to allow reuse

D. Use dynamic programming to store partial results and avoid recomputation

Solution

1. Step 1: Understand new constraint

   Cells can be reused multiple times, so marking visited cells to prevent reuse is no longer needed.

2. Step 2: Modify algorithm accordingly

   Removing in-place marking allows revisiting cells, correctly reflecting the relaxed constraint.

3. Step 3: Evaluate other options

   Keeping marking or using global visited set prevents reuse incorrectly; DP is not suitable here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Removing visited marking enables cell reuse as required [OK]

Hint: Relaxing constraints often means removing pruning steps [OK]

Common Mistakes:

• Keeping visited marking, causing false negatives
• Adding unnecessary global state