Expression Add Operators

Hard

#0269Time: O(4^n), where n is the length of the input string. At each position, we have 4 choices (3 operators + concatenation)Space: O(n) for recursion stack depth1 company

Patterns

Math Backtracking

Data structures

String

Companies

Prompt

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints:

1 <= num.length <= 10
num consists of only digits.
-2³¹ <= target <= 2³¹ - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses recursion to generate all possible combinations of operators between digits and evaluates each expression to find those that equal the target.

Algorithm

Start with an empty result list
For each position in the string:
- Try all possible numbers starting from that position
- For each valid number:
  - Try adding it with '+'
  - Try subtracting it with '-'
  - Try multiplying it with '*'
Keep track of the current evaluation and previous multiplied term
When reaching the end of string, check if evaluation equals target

Walkthrough

The idea is to try placing each operator (+, -, *) between every pair of digits and evaluate all resulting expressions. We'll use recursion to build expressions by adding one operator at a time.

For each position between digits, we have 4 choices:

Add '+' operator
Add '-' operator
Add '*' operator
Concatenate with next digit (no operator)

Here's the implementation:

1class Solution {2    public List<String> addOperators(String num, int target) {3        List<String> result = new ArrayList<>();4        if (num == null || num.length() == 0) return result;5        backtrack(result, num, target, 0, 0, 0, "");6        return result;7    }8    9    private void backtrack(List<String> result, String num, int target, int pos, 10                          long eval, long multed, String path) {11        if (pos == num.length()) {12            if (target == eval) result.add(path);13            return;14        }15        16        for (int i = pos; i < num.length(); i++) {17            if (i != pos && num.charAt(pos) == '0') break;18            long cur = Long.parseLong(num.substring(pos, i + 1));19            20            if (pos == 0) {21                backtrack(result, num, target, i + 1, cur, cur, path + cur);22            } else {23                backtrack(result, num, target, i + 1, eval + cur, cur, 24                         path + "+" + cur);25                backtrack(result, num, target, i + 1, eval - cur, -cur, 26                         path + "-" + cur);27                backtrack(result, num, target, i + 1, 28                         eval - multed + multed * cur, multed * cur, 29                         path + "*" + cur);30            }31        }32    }33}

Complexity

Time

O(4^n), where n is the length of the input string. At each position, we have 4 choices (3 operators + concatenation)

Space

O(n) for recursion stack depth

Trade-offs

Pros

Simple to understand and implement
Works for all valid input cases
Handles multiplication precedence correctly

Cons

Exponential time complexity
May be slow for longer input strings
Uses more memory due to recursive calls

This approach improves upon the brute force method by using memoization to cache intermediate results and avoid redundant calculations.

Algorithm

Use a hash map to store intermediate results
For each position:
- Generate valid numbers (handling leading zeros)
- Cache results for each state (position and remaining target)
- Combine cached results to build final expressions
Handle base cases and boundary conditions

Walkthrough

We can optimize the previous solution by caching intermediate results and pruning invalid paths early. We'll also handle overflow cases better.

1class Solution {2    private Map<String, List<String>> memo;3    4    public List<String> addOperators(String num, int target) {5        memo = new HashMap<>();6        return backtrackWithMemo(num, target, 0, num.length());7    }8    9    private List<String> backtrackWithMemo(String num, long target, int start, int len) {10        String key = start + "_" + target;11        if (memo.containsKey(key)) return memo.get(key);12        13        List<String> result = new ArrayList<>();14        15        // Base case: if we've used all digits16        if (start == len) {17            if (target == 0) result.add("");18            memo.put(key, result);19            return result;20        }21        22        // Handle leading zero case23        if (num.charAt(start) == '0') {24            List<String> next = backtrackWithMemo(num, target, start + 1, len);25            for (String expr : next) {26                result.add("0" + (expr.isEmpty() ? "" : "+" + expr));27            }28            memo.put(key, result);29            return result;30        }31        32        // Try different lengths of numbers starting at current position33        long curr = 0;34        for (int i = start; i < len; i++) {35            curr = curr * 10 + (num.charAt(i) - '0');36            if (curr > Integer.MAX_VALUE) break;37            38            List<String> next = backtrackWithMemo(num, target - curr, i + 1, len);39            for (String expr : next) {40                result.add(curr + (expr.isEmpty() ? "" : "+" + expr));41            }42        }43        44        memo.put(key, result);45        return result;46    }47}

Complexity

Time

O(4^n * n) worst case, but often better in practice due to memoization

Space

O(n * 4^n) to store memoized results

Trade-offs

Pros

Better performance for inputs with repeated patterns
Avoids redundant calculations
Handles overflow cases better
More memory efficient for certain inputs

Cons

Still has exponential complexity in worst case
Uses more memory for memoization
More complex implementation
May not be effective for inputs with few repeated subproblems

Solutions

Solution

1using System ; using System.Collections.Generic ; public class Expression { public long Value ; public override string ToString () { return Value . ToString (); } } public class BinaryExpression : Expression { public char Operator ; public Expression LeftChild ; public Expression RightChild ; public override string ToString () { return string . Format ( "{0}{1}{2}" , LeftChild , Operator , RightChild ); } } public class Solution { public IList < string > AddOperators ( string num , int target ) { var results = new List < string >(); if ( string . IsNullOrEmpty ( num )) return results ; this . num = num ; this . results = new List < Expression >[ num . Length , num . Length , 3 ]; foreach ( var ex in Search ( 0 , num . Length - 1 , 0 )) { if ( ex . Value == target ) { results . Add ( ex . ToString ()); } } return results ; } private string num ; private List < Expression >[,,] results ; private List < Expression > Search ( int left , int right , int level ) { if ( results [ left , right , level ] != null ) { return results [ left , right , level ]; } var result = new List < Expression >(); if ( level < 2 ) { for ( var i = left + 1 ; i <= right ; ++ i ) { List < Expression > leftResult , rightResult ; leftResult = Search ( left , i - 1 , level ); rightResult = Search ( i , right , level + 1 ); foreach ( var l in leftResult ) { foreach ( var r in rightResult ) { var newObjects = new List < Tuple < char , long >>(); if ( level == 0 ) { newObjects . Add ( Tuple . Create ( '+' , l . Value + r . Value )); newObjects . Add ( Tuple . Create ( '-' , l . Value - r . Value )); } else { newObjects . Add ( Tuple . Create ( '*' , l . Value * r . Value )); } foreach ( var newObject in newObjects ) { result . Add ( new BinaryExpression { Value = newObject . Item2 , Operator = newObject . Item1 , LeftChild = l , RightChild = r }); } } } } } else { if ( left == right || num [ left ] != '0' ) { long x = 0 ; for ( var i = left ; i <= right ; ++ i ) { x = x * 10 + num [ i ] - '0' ; } result . Add ( new Expression { Value = x }); } } if ( level < 2 ) { result . AddRange ( Search ( left , right , level + 1 )); } return results [ left , right , level ] = result ; } }

1class Solution { private List < String > ans ; private String num ; private int target ; public List < String > addOperators ( String num , int target ) { ans = new ArrayList <>(); this . num = num ; this . target = target ; dfs ( 0 , 0 , 0 , "" ); return ans ; } private void dfs ( int u , long prev , long curr , String path ) { if ( u == num . length ()) { if ( curr == target ) ans . add ( path ); return ; } for ( int i = u ; i < num . length (); i ++) { if ( i != u && num . charAt ( u ) == '0' ) { break ; } long next = Long . parseLong ( num . substring ( u , i + 1 )); if ( u == 0 ) { dfs ( i + 1 , next , next , path + next ); } else { dfs ( i + 1 , next , curr + next , path + "+" + next ); dfs ( i + 1 , - next , curr - next , path + "-" + next ); dfs ( i + 1 , prev * next , curr - prev + prev * next , path + "*" + next ); } } } }

1class Solution : def addOperators ( self , num : str , target : int ) -> List [ str ]: ans = [] def dfs ( start , prev_val , prev_sum , path ): if start == len ( num ) and prev_sum == target : ans . append ( path ) return # besides above if check, if start>len(num), it will not go inside for loop for i in range ( start , len ( num )): if i != start and num [ start ] == '0' : break curr_val = int ( num [ start : i + 1 ]) if start == 0 : # or, judege by 'path' string is empty or not dfs ( i + 1 , curr_val , curr_val , path + str ( curr_val )) else : dfs ( i + 1 , curr_val , prev_sum + curr_val , path + "+" + str ( curr_val )) dfs ( i + 1 , - curr_val , prev_sum - curr_val , path + "-" + str ( curr_val )) dfs ( i + 1 , prev_val * curr_val , # i.e. diff prev_sum - prev_val + prev_val * curr_val , path + "*" + str ( curr_val ), ) dfs ( 0 , 0 , 0 , "" ) return ans ############ class Solution ( object ): def addOperators ( self , num , target ): res , self . target = [], target for i in range ( 1 , len ( num ) + 1 ): if i == 1 or ( i > 1 and num [ 0 ] != "0" ): # prevent "00*" as a number self . dfs ( num [ i :], num [: i ], int ( num [: i ]), int ( num [: i ]), res ) # this step put first number in the string return res def dfs ( self , num , temp , cur , last , res ): if not num : if cur == self . target : res . append ( temp ) return for i in range ( 1 , len ( num ) + 1 ): val = num [: i ] if i == 1 or ( i > 1 and num [ 0 ] != "0" ): # prevent "00*" as a number self . dfs ( num [ i :], temp + "+" + val , cur + int ( val ), int ( val ), res ) self . dfs ( num [ i :], temp + "-" + val , cur - int ( val ), - int ( val ), res ) self . dfs ( num [ i :], temp + "*" + val , cur - last + last * int ( val ), last * int ( val ), res ) ''' cur - last + last * int(val) here the `cur` is the whole/accumlated result from previous recursions `cur` is NOT just the previous number '''

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem