Expression Add Operators

🎯

Expression Add Operators

hardBACKTRACKINGFacebookAmazonGoogle

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?

💡 This problem is about exploring all possible ways to insert operators between digits to form expressions that evaluate to a target. Beginners struggle because the search space is huge and handling operator precedence, especially multiplication, requires careful tracking of intermediate results.

📋

Problem Statement

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

💡

Example

Input"num = \"123\", target = 6"

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

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

Input"num = \"232\", target = 8"

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

Expressions 2*3+2=8 and 2+3*2=8 both match the target.

• num = "000", target = 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)
• num = "1", target = 1 → ["1"] (single digit equals target)

⚠️

Common Mistakes

Not handling leading zeros properly

Expressions like '05' are invalid but included, causing wrong answers

✅ Add a check to skip operands with leading zeros except single '0'

Incorrect multiplication handling

Multiplication evaluated incorrectly, e.g., '2+3*2' evaluated as (2+3)*2=10 instead of 2+(3*2)=8

✅ Track last operand and adjust evaluated value to respect operator precedence

Integer overflow when parsing operands

Runtime errors or incorrect results for large operands

✅ Use 64-bit integers (long/long long) or Python int which is unbounded

Not backtracking string builder length properly

Expressions get concatenated incorrectly, causing wrong outputs or runtime errors

✅ Reset string builder length after each recursive call to backtrack

Not testing edge cases like single digit or all zeros

Solution fails on minimal or tricky inputs

✅ Include edge cases in testing and handle them explicitly

🧠

Brute Force (Pure Recursion with Expression Building)

💡 This approach tries every possible way to insert operators between digits and evaluates the expression on the fly. It is the foundation to understand the problem's search space and operator handling.

Intuition

We recursively pick every possible operand substring and try all operators before it, tracking the current evaluated value and the last operand to handle multiplication correctly.

Algorithm

1. Start from index 0 and recursively try all possible splits of the remaining string as the next operand.
2. For each operand, if it's the first one, start the expression without an operator.
3. Otherwise, try adding '+', '-', and '*' operators before the operand and update the evaluated value accordingly.
4. Use a helper parameter to track the last operand value to correctly handle multiplication precedence.
5. If we reach the end of the string and the evaluated value equals the target, add the expression to results.

💡 The hardest part is tracking the evaluated value and last operand to correctly apply multiplication without evaluating the entire expression each time.

</>

Code

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    res = []
    def backtrack(index: int, path: str, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(path)
            return
        for i in range(index, len(num)):
            if i != index and num[index] == '0':
                break  # skip leading zero number
            curr_str = num[index:i+1]
            curr = int(curr_str)
            if index == 0:
                backtrack(i+1, curr_str, curr, curr)
            else:
                backtrack(i+1, path + '+' + curr_str, evaluated + curr, curr)
                backtrack(i+1, path + '-' + curr_str, evaluated - curr, -curr)
                backtrack(i+1, path + '*' + curr_str, evaluated - last_operand + last_operand * curr, last_operand * curr)
    backtrack(0, '', 0, 0)
    return res

# Driver code
if __name__ == '__main__':
    print(addOperators("123", 6))
    print(addOperators("00", 0))

Line Notes

def addOperators(num: str, target: int) -> List[str]:Defines main function with input types for clarity

def backtrack(index: int, path: str, evaluated: int, last_operand: int):Helper recursive function to build expressions and track evaluation

if index == len(num):Base case: if we've used all digits, check if expression evaluates to target

if i != index and num[index] == '0':Skip operands with leading zeros except single '0'

if index == 0:For first operand, start expression without operator

backtrack(i+1, path + '+' + curr_str, evaluated + curr, curr)Try adding '+' operator and update evaluated and last operand

backtrack(i+1, path + '-' + curr_str, evaluated - curr, -curr)Try adding '-' operator similarly

backtrack(i+1, path + '*' + curr_str, evaluated - last_operand + last_operand * curr, last_operand * curr)Handle multiplication by adjusting evaluated value to respect precedence

import java.util.*;

public class ExpressionAddOperators {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), num, target, 0, 0, 0);
        return res;
    }

    private void backtrack(List<String> res, StringBuilder path, String num, int target, int index, long evaluated, long lastOperand) {
        if (index == num.length()) {
            if (evaluated == target) {
                res.add(path.toString());
            }
            return;
        }
        int len = path.length();
        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == '0') break; // skip leading zero
            String currStr = num.substring(index, i + 1);
            long curr = Long.parseLong(currStr);
            if (index == 0) {
                path.append(currStr);
                backtrack(res, path, num, target, i + 1, curr, curr);
                path.setLength(len);
            } else {
                path.append('+').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated + curr, curr);
                path.setLength(len);

                path.append('-').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated - curr, -curr);
                path.setLength(len);

                path.append('*').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);
                path.setLength(len);
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        ExpressionAddOperators solver = new ExpressionAddOperators();
        System.out.println(solver.addOperators("123", 6));
        System.out.println(solver.addOperators("00", 0));
    }
}

Line Notes

public List<String> addOperators(String num, int target) {Main function signature returning list of expressions

backtrack(res, new StringBuilder(), num, target, 0, 0, 0);Start recursive backtracking with initial parameters

if (i != index && num.charAt(index) == '0') break;Skip operands with leading zeros

if (index == 0) {First operand added without operator

path.append('+').append(currStr);Try '+' operator and recurse

path.append('-').append(currStr);Try '-' operator and recurse

path.append('*').append(currStr);Try '*' operator and handle precedence

path.setLength(len);Backtrack by resetting path length after recursion

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

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        string path;
        backtrack(num, target, 0, 0, 0, path, res);
        return res;
    }

private:
    void backtrack(const string& num, int target, int index, long long evaluated, long long lastOperand, string& path, vector<string>& res) {
        if (index == num.size()) {
            if (evaluated == target) {
                res.push_back(path);
            }
            return;
        }
        int len = path.size();
        for (int i = index; i < num.size(); ++i) {
            if (i != index && num[index] == '0') break; // skip leading zero
            string currStr = num.substr(index, i - index + 1);
            long long curr = stoll(currStr);
            if (index == 0) {
                path += currStr;
                backtrack(num, target, i + 1, curr, curr, path, res);
                path.resize(len);
            } else {
                path += '+' + currStr;
                backtrack(num, target, i + 1, evaluated + curr, curr, path, res);
                path.resize(len);

                path += '-' + currStr;
                backtrack(num, target, i + 1, evaluated - curr, -curr, path, res);
                path.resize(len);

                path += '*' + currStr;
                backtrack(num, target, i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr, path, res);
                path.resize(len);
            }
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<string> res = sol.addOperators("123", 6);
    for (auto& expr : res) cout << expr << endl;
    cout << "---" << endl;
    res = sol.addOperators("00", 0);
    for (auto& expr : res) cout << expr << endl;
    return 0;
}

Line Notes

vector<string> addOperators(string num, int target) {Main function returning vector of valid expressions

backtrack(num, target, 0, 0, 0, path, res);Start recursive backtracking with initial parameters

if (i != index && num[index] == '0') break;Skip operands with leading zeros

if (index == 0) {First operand added without operator

path += '+' + currStr;Try '+' operator and recurse

path += '-' + currStr;Try '-' operator and recurse

path += '*' + currStr;Try '*' operator and handle precedence

path.resize(len);Backtrack by resetting path length after recursion

var addOperators = function(num, target) {
    const res = [];
    function backtrack(index, path, evaluated, lastOperand) {
        if (index === num.length) {
            if (evaluated === target) res.push(path);
            return;
        }
        for (let i = index; i < num.length; i++) {
            if (i !== index && num[index] === '0') break; // skip leading zero
            const currStr = num.substring(index, i + 1);
            const curr = Number(currStr);
            if (index === 0) {
                backtrack(i + 1, currStr, curr, curr);
            } else {
                backtrack(i + 1, path + '+' + currStr, evaluated + curr, curr);
                backtrack(i + 1, path + '-' + currStr, evaluated - curr, -curr);
                backtrack(i + 1, path + '*' + currStr, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);
            }
        }
    }
    backtrack(0, '', 0, 0);
    return res;
};

// Driver code
console.log(addOperators("123", 6));
console.log(addOperators("00", 0));

Line Notes

var addOperators = function(num, target) {Defines main function with parameters

function backtrack(index, path, evaluated, lastOperand) {Recursive helper to build expressions and track evaluation

if (i !== index && num[index] === '0') break;Skip operands with leading zeros

if (index === 0) {First operand added without operator

backtrack(i + 1, path + '+' + currStr, evaluated + curr, curr);Try '+' operator and recurse

backtrack(i + 1, path + '-' + currStr, evaluated - curr, -curr);Try '-' operator and recurse

backtrack(i + 1, path + '*' + currStr, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);Handle multiplication precedence

⏱

Complexity

TimeO(4^n) due to 3 operators and substring splits at each position

SpaceO(n) recursion stack and O(n) for building expressions

At each digit, we can choose to split or not and try 3 operators, leading to exponential growth in possibilities.

💡 For n=10, this means up to 1 million+ expressions to explore, which is why pruning and careful implementation matter.

Interview Verdict: Accepted but slow for large inputs

This approach is correct and foundational but inefficient for large inputs; it helps understand the problem deeply.

🧠

Backtracking with Early Pruning and Long Operand Handling

💡 This approach improves brute force by pruning invalid operands early (leading zeros) and using long integers to avoid overflow, making it more robust and slightly faster.

Intuition

By skipping invalid operands early and carefully managing operand parsing, we reduce unnecessary recursion and avoid errors from integer overflow.

Algorithm

1. At each recursion, skip operands with leading zeros immediately to avoid invalid expressions.
2. Use 64-bit integers (long/long long) to parse operands to prevent overflow.
3. Continue recursive exploration with the same logic as brute force but with these optimizations.
4. This reduces the search space and prevents runtime errors.

💡 The key improvement is pruning invalid operands early and safe operand parsing, which are common interview pitfalls.

</>

Code

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    res = []
    def backtrack(index: int, path: str, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(path)
            return
        for i in range(index, len(num)):
            if i != index and num[index] == '0':
                break  # prune leading zero
            curr_str = num[index:i+1]
            curr = int(curr_str)
            if index == 0:
                backtrack(i+1, curr_str, curr, curr)
            else:
                backtrack(i+1, path + '+' + curr_str, evaluated + curr, curr)
                backtrack(i+1, path + '-' + curr_str, evaluated - curr, -curr)
                backtrack(i+1, path + '*' + curr_str, evaluated - last_operand + last_operand * curr, last_operand * curr)
    backtrack(0, '', 0, 0)
    return res

# Driver code
if __name__ == '__main__':
    print(addOperators("105", 5))
    print(addOperators("00", 0))
    print(addOperators("3456237490", 9191))

Line Notes

if i != index and num[index] == '0':Prune operands with leading zeros early to avoid invalid expressions

curr = int(curr_str)Parse operand safely as integer; Python int can handle large numbers

if index == 0:First operand added without operator to start expression

backtrack(i+1, path + '*' + curr_str, evaluated - last_operand + last_operand * curr, last_operand * curr)Handle multiplication precedence by adjusting evaluated value

import java.util.*;

public class ExpressionAddOperators {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), num, target, 0, 0L, 0L);
        return res;
    }

    private void backtrack(List<String> res, StringBuilder path, String num, int target, int index, long evaluated, long lastOperand) {
        if (index == num.length()) {
            if (evaluated == target) {
                res.add(path.toString());
            }
            return;
        }
        int len = path.length();
        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == '0') break; // prune leading zero
            String currStr = num.substring(index, i + 1);
            long curr = Long.parseLong(currStr);
            if (index == 0) {
                path.append(currStr);
                backtrack(res, path, num, target, i + 1, curr, curr);
                path.setLength(len);
            } else {
                path.append('+').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated + curr, curr);
                path.setLength(len);

                path.append('-').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated - curr, -curr);
                path.setLength(len);

                path.append('*').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);
                path.setLength(len);
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        ExpressionAddOperators solver = new ExpressionAddOperators();
        System.out.println(solver.addOperators("105", 5));
        System.out.println(solver.addOperators("00", 0));
        System.out.println(solver.addOperators("3456237490", 9191));
    }
}

Line Notes

if (i != index && num.charAt(index) == '0') break;Prune invalid operands with leading zeros early

long curr = Long.parseLong(currStr);Use long to safely parse large operands

if (index == 0) {First operand added without operator

path.setLength(len);Backtrack by resetting path length after recursion

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

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        string path;
        backtrack(num, target, 0, 0, 0, path, res);
        return res;
    }

private:
    void backtrack(const string& num, int target, int index, long long evaluated, long long lastOperand, string& path, vector<string>& res) {
        if (index == num.size()) {
            if (evaluated == target) {
                res.push_back(path);
            }
            return;
        }
        int len = path.size();
        for (int i = index; i < num.size(); ++i) {
            if (i != index && num[index] == '0') break; // prune leading zero
            string currStr = num.substr(index, i - index + 1);
            long long curr = stoll(currStr);
            if (index == 0) {
                path += currStr;
                backtrack(num, target, i + 1, curr, curr, path, res);
                path.resize(len);
            } else {
                path += '+' + currStr;
                backtrack(num, target, i + 1, evaluated + curr, curr, path, res);
                path.resize(len);

                path += '-' + currStr;
                backtrack(num, target, i + 1, evaluated - curr, -curr, path, res);
                path.resize(len);

                path += '*' + currStr;
                backtrack(num, target, i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr, path, res);
                path.resize(len);
            }
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<string> res = sol.addOperators("105", 5);
    for (auto& expr : res) cout << expr << endl;
    cout << "---" << endl;
    res = sol.addOperators("00", 0);
    for (auto& expr : res) cout << expr << endl;
    cout << "---" << endl;
    res = sol.addOperators("3456237490", 9191);
    for (auto& expr : res) cout << expr << endl;
    return 0;
}

Line Notes

if (i != index && num[index] == '0') break;Prune operands with leading zeros early

long long curr = stoll(currStr);Use 64-bit integer to safely parse operands

if (index == 0) {First operand added without operator

path.resize(len);Backtrack by resetting path length after recursion

var addOperators = function(num, target) {
    const res = [];
    function backtrack(index, path, evaluated, lastOperand) {
        if (index === num.length) {
            if (evaluated === target) res.push(path);
            return;
        }
        for (let i = index; i < num.length; i++) {
            if (i !== index && num[index] === '0') break; // prune leading zero
            const currStr = num.substring(index, i + 1);
            const curr = Number(currStr);
            if (index === 0) {
                backtrack(i + 1, currStr, curr, curr);
            } else {
                backtrack(i + 1, path + '+' + currStr, evaluated + curr, curr);
                backtrack(i + 1, path + '-' + currStr, evaluated - curr, -curr);
                backtrack(i + 1, path + '*' + currStr, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);
            }
        }
    }
    backtrack(0, '', 0, 0);
    return res;
};

// Driver code
console.log(addOperators("105", 5));
console.log(addOperators("00", 0));
console.log(addOperators("3456237490", 9191));

Line Notes

if (i !== index && num[index] === '0') break;Prune invalid operands with leading zeros early

const curr = Number(currStr);Parse operand safely as number

if (index === 0) {First operand added without operator

backtrack(i + 1, path + '*' + currStr, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);Handle multiplication precedence

⏱

Complexity

TimeO(4^n) but with pruning reduces some branches

SpaceO(n) recursion stack and expression building

Pruning leading zeros cuts down invalid paths early, improving runtime but worst case remains exponential.

💡 Pruning can reduce millions of invalid paths, making the solution practical for typical interview inputs.

Interview Verdict: Accepted with better pruning

This approach is more robust and efficient than pure brute force, suitable for interviews.

🧠

Backtracking with StringBuilder / Mutable String for Performance

💡 This approach optimizes string concatenation by using mutable string builders (or equivalent) to reduce overhead, important in languages like Java and C++.

Intuition

Repeated string concatenation is expensive; using a mutable buffer and backtracking by resetting length improves performance.

Algorithm

1. Use a mutable string builder to build expressions incrementally.
2. At each recursion, append operand and operator, recurse, then reset builder length to backtrack.
3. This avoids creating new string objects repeatedly.
4. Logic for operand parsing, operator insertion, and evaluation remains the same.

💡 This optimization is subtle but important for performance in interviews where string operations dominate runtime.

</>

Code

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):
            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]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []

                path.append('-'); path.append(curr_str)
                backtrack(i+1, evaluated - curr, -curr)
                path[length_before:] = []

                path.append('*'); path.append(curr_str)
                backtrack(i+1, evaluated - last_operand + last_operand * curr, last_operand * curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

# Driver code
if __name__ == '__main__':
    print(addOperators("123", 6))
    print(addOperators("232", 8))

Line Notes

path = []Use list as mutable string builder for efficient concatenation

res.append(''.join(path))Join list elements to form final expression string

length_before = len(path)Record length before adding new operand/operator to backtrack later

path[length_before:] = []Backtrack by removing appended elements efficiently

import java.util.*;

public class ExpressionAddOperators {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        backtrack(res, path, num, target, 0, 0L, 0L);
        return res;
    }

    private void backtrack(List<String> res, StringBuilder path, String num, int target, int index, long evaluated, long lastOperand) {
        if (index == num.length()) {
            if (evaluated == target) {
                res.add(path.toString());
            }
            return;
        }
        int len = path.length();
        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == '0') break;
            String currStr = num.substring(index, i + 1);
            long curr = Long.parseLong(currStr);
            if (index == 0) {
                path.append(currStr);
                backtrack(res, path, num, target, i + 1, curr, curr);
                path.setLength(len);
            } else {
                path.append('+').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated + curr, curr);
                path.setLength(len);

                path.append('-').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated - curr, -curr);
                path.setLength(len);

                path.append('*').append(currStr);
                backtrack(res, path, num, target, i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);
                path.setLength(len);
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        ExpressionAddOperators solver = new ExpressionAddOperators();
        System.out.println(solver.addOperators("123", 6));
        System.out.println(solver.addOperators("232", 8));
    }
}

Line Notes

StringBuilder path = new StringBuilder();Use mutable string builder to avoid costly string concatenations

int len = path.length();Store length before recursion to backtrack efficiently

path.setLength(len);Reset builder length to backtrack after recursion

res.add(path.toString());Add built expression string to results

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

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        string path;
        backtrack(num, target, 0, 0, 0, path, res);
        return res;
    }

private:
    void backtrack(const string& num, int target, int index, long long evaluated, long long lastOperand, string& path, vector<string>& res) {
        if (index == num.size()) {
            if (evaluated == target) {
                res.push_back(path);
            }
            return;
        }
        int len = path.size();
        for (int i = index; i < num.size(); ++i) {
            if (i != index && num[index] == '0') break;
            string currStr = num.substr(index, i - index + 1);
            long long curr = stoll(currStr);
            if (index == 0) {
                path += currStr;
                backtrack(num, target, i + 1, curr, curr, path, res);
                path.resize(len);
            } else {
                path += '+' + currStr;
                backtrack(num, target, i + 1, evaluated + curr, curr, path, res);
                path.resize(len);

                path += '-' + currStr;
                backtrack(num, target, i + 1, evaluated - curr, -curr, path, res);
                path.resize(len);

                path += '*' + currStr;
                backtrack(num, target, i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr, path, res);
                path.resize(len);
            }
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<string> res = sol.addOperators("123", 6);
    for (auto& expr : res) cout << expr << endl;
    cout << "---" << endl;
    res = sol.addOperators("232", 8);
    for (auto& expr : res) cout << expr << endl;
    return 0;
}

Line Notes

string path;Mutable string used as builder to efficiently append and backtrack

int len = path.size();Store length before recursion to backtrack

path.resize(len);Reset string length to backtrack after recursion

res.push_back(path);Add current expression to results when target matched

var addOperators = function(num, target) {
    const res = [];
    const path = [];
    function backtrack(index, evaluated, lastOperand) {
        if (index === num.length) {
            if (evaluated === target) res.push(path.join(''));
            return;
        }
        for (let i = index; i < num.length; i++) {
            if (i !== index && num[index] === '0') break;
            const currStr = num.substring(index, i + 1);
            const curr = Number(currStr);
            const lengthBefore = path.length;
            if (index === 0) {
                path.push(currStr);
                backtrack(i + 1, curr, curr);
                path.length = lengthBefore;
            } else {
                path.push('+', currStr);
                backtrack(i + 1, evaluated + curr, curr);
                path.length = lengthBefore;

                path.push('-', currStr);
                backtrack(i + 1, evaluated - curr, -curr);
                path.length = lengthBefore;

                path.push('*', currStr);
                backtrack(i + 1, evaluated - lastOperand + lastOperand * curr, lastOperand * curr);
                path.length = lengthBefore;
            }
        }
    }
    backtrack(0, 0, 0);
    return res;
};

// Driver code
console.log(addOperators("123", 6));
console.log(addOperators("232", 8));

Line Notes

const path = [];Use array as mutable string builder for efficient concatenation

res.push(path.join(''));Join array elements to form expression string when adding to results

const lengthBefore = path.length;Store length before recursion to backtrack

path.length = lengthBefore;Reset array length to backtrack after recursion

⏱

Complexity

TimeO(4^n) but faster due to efficient string operations

SpaceO(n) recursion stack and mutable string builder

Using mutable strings reduces overhead of string copying, improving runtime in practice.

💡 This optimization is crucial in languages where string concatenation is costly, like Java and C++.

Interview Verdict: Accepted with performance optimization

This approach is recommended for interviews to demonstrate attention to performance details.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimized backtracking with pruning and mutable strings is best to balance clarity and performance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(4^n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code due to inefficiency
2. Backtracking with Pruning	O(4^n) but fewer branches	O(n)	Yes	Yes	Good to code for correctness and pruning demonstration
3. Backtracking with Mutable String Builder	O(4^n) optimized	O(n)	Yes	Yes	Best approach to code for performance and clarity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize step-by-step, and finally code with confidence.

How to Present

Step 1: Clarify input, output, and constraints with the interviewer.Step 2: Describe the brute force recursive approach to try all operator insertions.Step 3: Explain how to track evaluation and handle multiplication precedence.Step 4: Discuss pruning invalid operands with leading zeros.Step 5: Mention performance optimizations like using mutable strings.Step 6: Code the solution carefully, testing edge cases.

Time Allocation

Clarify: 3min → Approach: 7min → Code: 15min → Test: 5min. Total ~30min

What the Interviewer Tests

The interviewer tests your understanding of recursion, backtracking, operator precedence, pruning invalid inputs, and coding correctness.

Common Follow-ups

• What if division operator is added? → Need to handle division carefully with integer division and zero division checks.
• How to handle very large numbers? → Use long integers or BigInteger types to avoid overflow.

💡 These follow-ups test your ability to extend the solution and handle edge cases beyond the base problem.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to generate all expressions by inserting operators between digits to meet a target, especially when operator precedence matters.

Signature Phrases

add binary operatorsevaluate expression to targetno leading zeros

NOT This Pattern When

This is not a dynamic programming problem because it requires generating all valid expressions, not just counting or optimizing.

Similar Problems

Different Ways to Add Parentheses - explores all ways to parenthesize expressionsBasic Calculator II - evaluates expressions with operator precedenceRestore IP Addresses - backtracking with substring partitioning and validation

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 possible letter combinations that a given digit string could represent on a phone keypad, where each digit maps to a set of letters. Which algorithmic approach guarantees generating all valid combinations efficiently without missing any or producing duplicates?

easy

A. Greedy algorithm that picks the first letter for each digit to form a single combination

B. Sorting digits and using binary search to find letter combinations

C. Dynamic programming that stores partial combinations to avoid recomputation

D. Backtracking that explores all letter choices for each digit recursively

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all possible letter combinations for each digit, which means exploring all letter choices for every digit.

2. Step 2: Identify suitable algorithm

   Backtracking recursively explores all letter options per digit, ensuring no combination is missed or duplicated. Greedy or sorting approaches do not explore all combinations, and DP is not naturally suited here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking systematically enumerates all combinations [OK]

Hint: Backtracking explores all letter choices per digit [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all combinations
• Confusing DP with backtracking here

3. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?

easy

A. Scan from the end to find a pivot where the sequence stops increasing, swap with the smallest greater element on the right, then reverse the suffix.

B. Apply a greedy approach by swapping the first two elements that are out of order from the start.

C. Use dynamic programming to store all permutations and find the next one by memoization.

D. Generate all permutations, sort them, and pick the next one after the current permutation.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.

2. Step 2: Identify the optimal approach

   The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]

Hint: Next permutation uses pivot-swap-reverse pattern [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using greedy from start fails on suffix order

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

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