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.