Expression Add Operators

📋

Problem

Imagine you are building a calculator app that can insert operators between digits to reach a target value. How do you find all valid expressions that evaluate exactly to that target?

Given a string num that contains only digits and an integer target, return all possibilities to add binary operators ('+', '-', or '*') between the digits so that the resultant expression evaluates to the target value. The returned expressions should not contain any spaces and must not have leading zeros in any operand except for the number zero itself.

1 ≤ num.length ≤ 10num consists of only digits.-2^31 ≤ target ≤ 2^31 - 1

Edge cases: num = "000", target = 0 → ["0+0+0", "0+0-0", "0+0*0", "0-0+0", "0-0-0", "0-0*0", "0*0+0", "0*0-0", "0*0*0"]num = "105", target = 5 → ["1*0+5", "10-5"] (leading zero in '05' is invalid)num = "3456237490", target = 9191 → [] (no valid expressions)

</>

IDE

def addOperators(num: str, target: int) -> list:public List<String> addOperators(String num, int target)vector<string> addOperators(string num, int target)function addOperators(num, target)

def addOperators(num: str, target: int) -> list:
    # Write your solution here
    pass

class Solution {
    public List<String> addOperators(String num, int target) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> addOperators(string num, int target) {
    // Write your solution here
    return {};
}

function addOperators(num, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1+2+3Missing multiplication operator expressions due to ignoring multiplication precedence.✅ Track last operand and adjust evaluated value when '*' operator is used: evaluated = evaluated - last_operand + last_operand * current.

Wrong: 1*0+510-51*05Allowing operands with leading zeros like '05' which are invalid.✅ Add check to skip operands starting with '0' if length > 1.

Wrong: 0+0+00+0-00-0+00-0-00*0*000+0Allowing multi-digit operands with leading zeros like '00'.✅ Only allow single '0' as operand; skip multi-digit operands starting with '0'.

Wrong: 2+2+22+2+22+2+22*2*22*2*22*2*2Reusing digits or generating duplicate expressions due to incorrect index advancement.✅ Advance index correctly in recursion to use each digit exactly once and avoid duplicates.

Wrong: Solution times out on large inputs due to exponential complexity.✅ Implement pruning and efficient string building to reduce runtime.

✓

Test Cases

Focus on handling base cases like empty input and single digits correctly.

Ensure correct operator precedence and operand validation to avoid subtle bugs.

Optimize your backtracking with pruning and efficient string operations.

t1_01basic

Input{"num":"123","target":6}

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

⏱ Performance - must finish in 2000ms

Both expressions evaluate to 6: 1+2+3=6 and 1*2*3=6.

💡 Try building expressions by inserting operators between digits.

💡 Use backtracking to explore all operator combinations and evaluate expressions.

💡 Track the current evaluated value and last operand to handle multiplication correctly.

Why it failed: Incorrect or missing expressions for target 6. Likely missing multiplication handling or incorrect evaluation logic. Fix by tracking last operand and adjusting evaluated value when '*' operator is used.

✓ Correctly generates all expressions evaluating to target 6.

t1_02basic

Input{"num":"232","target":8}

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

⏱ Performance - must finish in 2000ms

Expressions '2*3+2' and '2+3*2' both evaluate to 8.

💡 Consider operator precedence when evaluating expressions.

💡 Use backtracking with tracking of last operand to correctly handle multiplication.

💡 Avoid leading zeros in operands except for zero itself.

Why it failed: Missing valid expressions or incorrect evaluation for target 8. Possibly ignoring operator precedence or leading zero rules. Fix by implementing correct multiplication undo logic and skipping operands with leading zeros.

✓ Correctly finds all valid expressions evaluating to 8.

t2_01edge

Input{"num":"","target":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input string yields no expressions.

💡 Check how your code handles empty input strings.

💡 Ensure base case returns empty list when no digits are available.

💡 Return empty list immediately if input string is empty.

Why it failed: Code crashes or returns non-empty list on empty input. Fix by adding base case to return empty list if num is empty.

✓ Correctly returns empty list for empty input.

t2_02edge

Input{"num":"1","target":1}

Expected["1"]

⏱ Performance - must finish in 2000ms

Single digit equal to target returns single expression without operators.

💡 Handle single digit input as a base case.

💡 Return the digit itself if it equals the target.

💡 Avoid adding operators when only one digit is present.

Why it failed: Fails to return single digit expression when num length is 1. Fix by checking if entire num equals target and returning it as a valid expression.

✓ Correctly returns single digit expression matching target.

t2_03edge

Input{"num":"000","target":0}

Expected["0+0+0","0+0-0","0+0*0","0-0+0","0-0-0","0-0*0","0*0+0","0*0-0","0*0*0"]

⏱ Performance - must finish in 2000ms

All combinations of operators between zeros evaluate to 0; leading zeros allowed only for zero itself.

💡 Handle operands with zero carefully to avoid invalid leading zeros.

💡 Allow '0' as a valid operand but disallow '00', '000', etc.

💡 Generate all operator combinations between zeros and verify evaluation.

Why it failed: Incorrectly skipping valid zero operands or generating invalid leading zero operands. Fix by allowing single '0' operands and skipping multi-digit operands starting with '0'.

✓ Correctly generates all valid expressions with zeros evaluating to target 0.

t3_01corner

Input{"num":"105","target":5}

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

⏱ Performance - must finish in 2000ms

Expressions with valid leading zero handling: '05' is invalid, so '1*0+5' and '10-5' are valid.

💡 Check for leading zeros in operands and skip invalid ones.

💡 Operands like '05' are invalid; only '0' alone is valid zero operand.

💡 Implement condition to break loop if operand starts with '0' and length > 1.

Why it failed: Incorrectly allowing operands with leading zeros like '05'. Fix by adding check to skip operands with leading zeros except single '0'. This is the leading zero validation test.

✓ Correctly handles leading zero constraints.

t3_02corner

Input{"num":"1234","target":11}

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

⏱ Performance - must finish in 2000ms

Expressions that require correct multiplication undo logic to evaluate properly. Note '1+2+3+4' also evaluates to 11 and is valid.

💡 Track last operand to correctly handle multiplication precedence.

💡 When adding '*', subtract last operand and add last operand multiplied by current.

💡 Update evaluated value as evaluated - last_operand + last_operand * current.

Why it failed: Incorrect evaluation of expressions with multiplication due to missing undo logic. Fix by tracking last operand and adjusting evaluated value accordingly. Also include all valid expressions like '1+2+3+4'. This is the multiplication undo bug test.

✓ Correctly evaluates expressions with multiplication.

t3_03corner

Input{"num":"222","target":6}

Expected["2+2+2","2+2*2","2*2*2"]

⏱ Performance - must finish in 2000ms

Tests that operators are used exactly once per split and no unbounded reuse of operands. '2+2*2' also evaluates to 6 and is valid.

💡 Ensure each digit is used exactly once in order without reuse.

💡 Do not treat problem as unbounded operator insertion; only between digits.

💡 Backtrack by moving index forward and not reusing previous digits.

Why it failed: Incorrectly reusing digits or generating duplicate expressions due to incorrect index advancement. Fix by advancing index correctly in recursion to use each digit exactly once and avoid duplicates. Also include all valid expressions like '2+2*2'. This is the 0/1 usage constraint test.

✓ Correctly uses each digit once and generates valid expressions.

t4_01performance

Input{"num":"1234567890","target":100}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=10 with backtracking O(4^n) complexity must complete within 2 seconds.

💡 Backtracking has exponential time complexity O(4^n).

💡 Prune branches early when partial evaluation cannot reach target.

💡 Use efficient string building and memoization if possible.

Why it failed: Solution times out due to exponential complexity O(4^n). Optimize by pruning invalid branches and using efficient string operations.

✓ Solution completes within time limit confirming expected complexity.

Practice

1. Given the following code for next permutation, what is the content of the array nums after calling next_permutation([1, 3, 2])?

easy

A. [1, 2, 3]

B. [2, 3, 1]

C. [2, 1, 3]

D. [1, 3, 2]

Solution

1. Step 1: Trace the pivot search

   Start with i = 1 (index of 3). Since nums[1]=3 >= nums[2]=2, decrement i to 0. nums[0]=1 < nums[1]=3, so pivot i=0.

2. Step 2: Find j to swap with pivot

   Start j=2 (value 2). nums[2]=2 > nums[0]=1, so j=2. Swap nums[0] and nums[2]: array becomes [2,3,1]. Then reverse suffix from i+1=1 to end: reverse [3,1] -> [1,3]. Final array: [2,1,3].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Array changes from [1,3,2] to [2,1,3] after next permutation [OK]

Hint: Pivot found at first decreasing from right, swap and reverse suffix [OK]

Common Mistakes:

• Swapping with wrong element
• Not reversing suffix after swap

2. 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

3. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?

medium

A. O(2^{2n} * n) because it generates all sequences and checks validity

B. O(n^2) because it builds sequences of length 2n with nested loops

C. O(n!) because it permutes parentheses positions

D. O(\frac{4^n}{n^{3/2}}) because the number of valid sequences is the nth Catalan number

Solution

1. Step 1: Identify number of valid sequences

   The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).

2. Step 2: Analyze backtracking time

   Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known Catalan number growth for valid parentheses [OK]

Hint: Catalan number growth dominates complexity [OK]

Common Mistakes:

• Confusing brute force with backtracking complexity
• Assuming factorial complexity

4. The following code attempts to solve N-Queens using bitmask backtracking. Which line contains a subtle bug that can cause invalid solutions or missed solutions?

medium

A. Line extracting rightmost 1-bit as position

B. Line updating diag1 and diag2 with incorrect bit shifts in recursive call

C. Line computing available_positions with bitmask and negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify bit shift directions for diagonals

   diag1 (major diagonal) must be shifted left by 1, diag2 (minor diagonal) shifted right by 1 to reflect next row attacks.

2. Step 2: Check recursive call shifts

   The code incorrectly shifts diag1 right and diag2 left, reversing the attack directions, causing invalid pruning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct diagonal shifts are diag1 << 1 and diag2 >> 1 [OK]

Hint: Diagonal attack masks must shift opposite directions each row [OK]

Common Mistakes:

• Swapping diag1 and diag2 shifts
• Not resetting board after recursion
• Incorrect bitmask negation

5. Suppose you want to modify the palindrome partitioning algorithm to allow reuse of substrings in partitions (i.e., substrings can appear multiple times in different partitions). Which change to the algorithm is necessary to correctly handle this variant without losing valid partitions or causing duplicates?

hard

A. Memoize palindrome checks and reuse results but keep backtracking unchanged

B. Modify backtracking to avoid popping from path to reuse substrings across calls

C. Use a global visited set to skip substrings already used in previous partitions

D. Allow substrings to be reused by resetting path after each complete partition

Solution

1. Step 1: Understand reuse requirement

   Reusing substrings means substrings can appear multiple times in different partitions, so path management must allow multiple uses.

2. Step 2: Identify necessary algorithm change

   Memoizing palindrome checks improves efficiency by avoiding repeated palindrome computations, while backtracking logic remains unchanged to generate all valid partitions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization optimizes palindrome checks without affecting partition generation correctness [OK]

Hint: Memoize palindrome checks to optimize without changing backtracking [OK]

Common Mistakes:

• Assuming popping affects substring reuse
• Using visited sets that block valid reuse
• Resetting path incorrectly losing partitions