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 count the number of permutations of numbers from 1 to n such that for each position i, either the number at position i is divisible by i or i is divisible by the number. Which algorithmic approach best guarantees an efficient solution?

easy

A. Sorting numbers and checking divisibility in a single pass

B. Greedy algorithm that places numbers based on divisibility from left to right

C. Dynamic programming with memoization over subsets

D. Backtracking with pruning to explore valid permutations only

Solution

1. Step 1: Understand problem constraints

   The problem requires counting permutations with divisibility conditions at each position, which is a combinatorial search problem.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning efficiently explores only valid permutations, avoiding full enumeration, unlike greedy or sorting approaches which fail to guarantee correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking prunes invalid branches early, ensuring correctness and efficiency [OK]

Hint: Backtracking prunes invalid permutations early [OK]

Common Mistakes:

• Assuming greedy can solve divisibility constraints
• Thinking sorting suffices for permutation constraints

2. You need to find the k-th lexicographically smallest permutation of numbers from 1 to n. Which approach guarantees an optimal solution without generating all permutations explicitly?

easy

A. Use a greedy algorithm that swaps elements to reach the k-th permutation directly.

B. Compute factorial values to determine each digit's position and build the permutation directly.

C. Use dynamic programming to count permutations and reconstruct the k-th sequence.

D. Generate all permutations using backtracking and return the k-th one.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the k-th permutation without enumerating all permutations, which is infeasible for large n.

2. Step 2: Identify the approach that uses factorial number system

   Using precomputed factorials, we can determine the index of each digit in the permutation directly, avoiding full enumeration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Factorial-based direct computation is optimal and avoids timeouts [OK]

Hint: Factorials let you jump directly to the k-th permutation [OK]

Common Mistakes:

• Thinking greedy swaps can find k-th permutation efficiently
• Assuming DP is needed here
• Trying to generate all permutations for large n

3. Consider the following snippet from an optimized Sudoku solver using backtracking with heuristics. Given the board below, what is the length of candidates for the first empty cell chosen after sorting empties by candidate count? Board: [['5', '3', '.', '.', '7', '.', '.', '.', '.'], ['6', '.', '.', '1', '9', '5', '.', '.', '.'], ['.', '9', '8', '.', '.', '.', '.', '6', '.'], ['8', '.', '.', '.', '6', '.', '.', '.', '3'], ['4', '.', '.', '8', '.', '3', '.', '.', '1'], ['7', '.', '.', '.', '2', '.', '.', '.', '6'], ['.', '6', '.', '.', '.', '.', '2', '8', '.'], ['.', '.', '.', '4', '1', '9', '.', '.', '5'], ['.', '.', '.', '.', '8', '.', '.', '7', '9']] Code snippet:

def get_candidates(r, c):
    b = (r//3)*3 + c//3
    return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
first_empty = empties[0]
candidates_len = len(get_candidates(first_empty[0], first_empty[1]))

What is the value of candidates_len?

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify first empty cell after sorting

   Check empties and compute candidates for each; the cell with fewest candidates is chosen first.

2. Step 2: Calculate candidates for first empty cell (0,2)

   Row 0 has {'5','3','7'}, column 2 has {'8'}, box 0 has {'5','3','6','9','8'}. Candidates are digits not in any of these sets: '1','2','4'. So length is 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting candidates for (0,2) yields 3 [OK]

Hint: Count candidates by excluding row, column, box digits [OK]

Common Mistakes:

• Forgetting box constraints
• Miscounting candidates for first empty cell

4. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?

medium

A. O(n * 4^n) because we process each digit and expand combinations exponentially

B. O(2^n) because each digit doubles the number of combinations

C. O(4^n * n) because there are up to 4^n combinations and each combination is built with n concatenations

D. O(n^2) because we process n digits and each combination takes n steps

Solution

1. Step 1: Identify number of combinations

   Each digit maps to up to 4 letters, so total combinations are up to 4^n.

2. Step 2: Analyze work per combination

   Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.

3. Step 3: Simplify complexity expression

   O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Time is exponential in n with linear cost per combination [OK]

Hint: Exponential combinations times linear build cost [OK]

Common Mistakes:

• Confusing exponential base (2 vs 4)
• Ignoring concatenation cost per combination

5. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily