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. Consider the following bitmask-based backtracking code for n=4. After placing the first queen at row 0, column 1, what is the value of available_positions at row 1 (second recursive call)?

easy

A. 0b1010 (binary 10 decimal)

B. 0b1100 (binary 12 decimal)

C. 0b1001 (binary 9 decimal)

D. 0b1000 (binary 8 decimal)

Solution

1. Step 1: Trace first queen placement at row 0, col 1

   Position bitmask = 0b0010 (decimal 2). Update cols=0b0010, diag1=(0b0010)<<1=0b0100, diag2=(0b0010)>>1=0b0001.

2. Step 2: Compute available_positions at row 1

   available_positions = (0b1111) & ~(cols | diag1 | diag2) = 0b1111 & ~(0b0010 | 0b0100 | 0b0001) = 0b1111 & ~0b0111 = 0b1111 & 0b1000 = 0b1000 (decimal 8). The only available position is column 3 (bit 3).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask after first queen excludes cols 1, diag1 shifted left, diag2 shifted right [OK]

Hint: Bitmask tracks attacked columns and diagonals precisely [OK]

Common Mistakes:

• Miscomputing diagonal shifts
• Off-by-one in bit length
• Confusing cols with diag masks

2. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

3. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

Hint: Always append a copy of mutable lists to results [OK]

Common Mistakes:

• Forgetting to copy before appending results in duplicate references

4. What is the time complexity of the optimal iterative backtracking solution with pruning for restoring IP addresses from a string of length n, and why?

medium

A. O(3^4) because each of the 4 segments can be length 1 to 3, and pruning limits exploration

B. O(4^n) because each character can start a new segment or continue the previous one

C. O(n^4) because we try all partitions of the string into 4 segments

D. O(n!) due to permutations of segment lengths

Solution

1. Step 1: Identify branching factor per segment

   Each segment can be length 1, 2, or 3, so branching factor is at most 3 per segment.

2. Step 2: Calculate total combinations

   There are 4 segments, so total combinations are at most 3^4 = 81. Pruning further reduces this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time complexity depends on fixed 4 segments with max 3 choices each [OK]

Hint: Fixed 4 segments with max 3 lengths each -> 3^4 complexity [OK]

Common Mistakes:

• Assuming complexity depends on n^4
• Confusing permutations with combinations

5. Suppose the problem is modified so that IP address segments can be reused multiple times (i.e., segments can overlap and be repeated). Which modification to the backtracking algorithm correctly handles this variant without generating duplicates or invalid IPs?

hard

A. Remove the pruning condition on remaining characters and segments to allow overlapping segments

B. Use a memoization cache keyed by (start, segments formed) to avoid recomputing paths

C. Allow segments to be reused by resetting start index to previous segment start after each addition

D. Change the algorithm to generate all permutations of segments without pruning

Solution

1. Step 1: Understand reuse implies overlapping segments

   Allowing reuse means the same substring can be used multiple times, potentially causing repeated computations.

2. Step 2: Apply memoization to avoid duplicates

   Memoization keyed by (start, segments formed) prevents recomputing the same subproblems and avoids duplicates.

3. Step 3: Evaluate other options

   Removing pruning causes inefficiency; resetting start index breaks segment order; generating all permutations ignores validity and pruning.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization efficiently handles reuse without duplicates [OK]

Hint: Memoization avoids recomputation when segments can be reused [OK]

Common Mistakes:

• Removing pruning causes timeouts
• Resetting start index breaks segment order