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 Python code for generating parentheses, what is the content of result after calling generateParenthesis(2)?

easy

A. ['((', '))']

B. ['()()', '(())']

C. ['(())', '()()']

D. ['()()', '(()']

Solution

1. Step 1: Trace backtrack calls for n=2

   Sequences generated are '(())' and '()()' in that order due to DFS with backtracking.

2. Step 2: Confirm order and validity

   Both sequences are valid balanced parentheses of length 4, matching expected output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches known valid sequences for n=2 [OK]

Hint: Backtracking generates sequences in DFS order [OK]

Common Mistakes:

• Confusing order of sequences
• Including invalid partial sequences

2. You need to generate all unique permutations of an array that may contain duplicate elements. Which approach guarantees generating all unique permutations efficiently without producing duplicates during generation?

easy

A. Use a greedy algorithm that picks the smallest unused element at each step.

B. Use backtracking with sorting and a mechanism to skip duplicates during recursion.

C. Use dynamic programming to build permutations from smaller subproblems.

D. Generate all permutations and then filter duplicates using a hash set.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating all unique permutations of an array with duplicates, so duplicates must be avoided during generation to be efficient.

2. Step 2: Evaluate approaches

   Greedy algorithms do not guarantee all permutations; DP is not suitable here; generating all permutations and filtering duplicates is correct but inefficient. Backtracking with sorting and skipping duplicates during recursion ensures duplicates are pruned early.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with duplicate skipping is the standard optimal approach [OK]

Hint: Skip duplicates during backtracking after sorting [OK]

Common Mistakes:

• Thinking greedy or DP can generate unique permutations efficiently

3. You are given a partially filled 9x9 grid where each row, column, and 3x3 sub-box must contain digits 1 through 9 without repetition. Which algorithmic approach guarantees finding a valid solution if one exists?

easy

A. Greedy algorithm that fills cells with the first valid digit found

B. Breadth-first search exploring all possible digit placements simultaneously

C. Dynamic programming by storing subproblems of partially filled grids

D. Backtracking with constraint propagation and heuristic ordering of empty cells

Solution

1. Step 1: Understand problem constraints

   The problem requires filling cells respecting row, column, and box constraints, which is a classic constraint satisfaction problem.

2. Step 2: Identify algorithm that guarantees solution

   Backtracking with constraint propagation prunes invalid choices early, and heuristic ordering reduces branching, ensuring completeness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Constraint propagation + heuristic ordering is standard for Sudoku solvers [OK]

Hint: Constraint satisfaction problems need backtracking with pruning [OK]

Common Mistakes:

• Assuming greedy or BFS alone can solve Sudoku efficiently

4. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

5. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.