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. Consider the following code snippet for computing the maximum path sum in a binary tree. Given the tree with root value 1, left child 2, and right child 3, what is the final returned maximum path sum?

easy

A. 3

B. 6

C. 5

D. 4

Solution

1. Step 1: Trace helper on left child (2):

   left and right children are null, so left=0, right=0, max_sum updated to max(-inf, 2+0+0)=2, returns 2+max(0,0)=2.

2. Step 2: Trace helper on right child (3):

   Similarly, max_sum updated to max(2, 3+0+0)=3, returns 3+max(0,0)=3.

3. Step 3: Trace helper on root (1):

   left=2, right=3, max_sum updated to max(3, 1+2+3)=6, returns 1+max(2,3)=4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Max path is 2 -> 1 -> 3 with sum 6 [OK]

Hint: Sum includes node plus max gains from both children [OK]

Common Mistakes:

• Returning sum of one child only
• Off-by-one in max_sum update
• Ignoring zero cutoff for negative gains

2. What is the time complexity of the optimal Alien Dictionary solution using Kahn's algorithm with early cycle detection and edge deduplication, given C as the total number of characters in all words and U as the number of unique characters?

medium

A. O(C log U) due to sorting characters during graph construction

B. O(U^2) due to checking all pairs of characters

C. O(C * U) because each character is compared with all unique characters

D. O(C + U + E) where E is number of edges, since graph construction and BFS visit all characters and edges once

Solution

1. Step 1: Analyze graph construction cost

   Each adjacent word pair is compared up to min length, total comparisons proportional to total characters C.

2. Step 2: Analyze topological sort cost

   BFS visits each node (U) and each edge (E) once; E ≤ C since edges come from character comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity O(C + U + E) matches linear graph traversal [OK]

Hint: Graph traversal cost dominates, not pairwise character comparisons [OK]

Common Mistakes:

• Assuming quadratic due to character pairs
• Confusing edges with nodes
• Forgetting BFS linearity

3. What is the time complexity of the optimized recursive approach with global tracking for the Binary Tree Maximum Path Sum problem, assuming the tree has n nodes and height h?

medium

A. O(n^2) because at each node, sums of all paths in subtrees are computed

B. O(n \times h) due to recursive calls and path computations at each node

C. O(n) because each node is visited once and constant work is done per node

D. O(h) because recursion depth limits the number of calls

Solution

1. Step 1: Identify that each node is visited exactly once in the recursive traversal.

   The helper function is called once per node, doing constant work (max, addition) per call.

2. Step 2: Confirm that no nested loops or repeated subtree computations occur.

   The recursion does not recompute subtrees multiple times, so total work is proportional to n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node -> O(n) [OK]

Hint: Each node processed once with constant work [OK]

Common Mistakes:

• Assuming O(n^2) due to path sums
• Confusing recursion depth with total calls
• Ignoring constant work per node

4. The following code attempts to solve the Russian Doll Envelopes problem optimally. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes with key (x[0], x[1]) ascending both

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing tails element at found index

Solution

1. Step 1: Examine sorting key

   Sorting by (width asc, height asc) allows envelopes with same width and increasing height, which breaks strict nesting rules.

2. Step 2: Correct sorting key

   Sorting by (width asc, height desc) prevents envelopes with equal width but increasing height from being counted incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing sorting to (x[0], -x[1]) fixes the bug [OK]

Hint: Sort height descending for equal widths to avoid counting duplicates [OK]

Common Mistakes:

• Sorting both width and height ascending
• Using <= instead of < in comparisons
• Not handling equal widths properly

5. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output by adding redundant points or missing height changes?

medium

A. Line where maxH is computed with max(h1, h2)

B. Line where merged appends [x, maxH] without checking last height

C. Line where i and j are incremented in the else block

D. Line where h1 and h2 are initialized to 0 at the start

Solution

1. Step 1: Identify the bug

   The code appends every point without checking if the height changed, causing redundant points.

2. Step 2: Correct approach

   Appending should happen only if merged is empty or last height differs from maxH to avoid duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending unconditionally causes redundant points [OK]

Hint: Check if last height differs before appending new point [OK]

Common Mistakes:

• Appending points even if height unchanged
• Incorrectly incrementing indices causing skips
• Not initializing heights properly