# Expression Add Operators
**Difficulty:** HARD
[External](https://leetcode.com/problems/expression-add-operators)
Canonical: https://scaleengineer.com/dsa/problems/expression-add-operators
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
**Companies:** [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
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.
* `-231 <= target <= 231 - 1`

# Approaches
## Brute Force with Recursion
This approach uses recursion to generate all possible combinations of operators between digits and evaluates each expression to find those that equal the target.
**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
**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
### Explanation
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:
1. Add '+' operator
2. Add '-' operator
3. Add '*' operator
4. Concatenate with next digit (no operator)

Here's the implementation:

```java
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        if (num == null || num.length() == 0) return result;
        backtrack(result, num, target, 0, 0, 0, "");
        return result;
    }
    
    private void backtrack(List<String> result, String num, int target, int pos, 
                          long eval, long multed, String path) {
        if (pos == num.length()) {
            if (target == eval) result.add(path);
            return;
        }
        
        for (int i = pos; i < num.length(); i++) {
            if (i != pos && num.charAt(pos) == '0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            
            if (pos == 0) {
                backtrack(result, num, target, i + 1, cur, cur, path + cur);
            } else {
                backtrack(result, num, target, i + 1, eval + cur, cur, 
                         path + "+" + cur);
                backtrack(result, num, target, i + 1, eval - cur, -cur, 
                         path + "-" + cur);
                backtrack(result, num, target, i + 1, 
                         eval - multed + multed * cur, multed * cur, 
                         path + "*" + cur);
            }
        }
    }
}
```
### Algorithm
1. Start with an empty result list
2. 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 '*'
3. Keep track of the current evaluation and previous multiplied term
4. When reaching the end of string, check if evaluation equals target

## Optimized Backtracking with Memoization
This approach improves upon the brute force method by using memoization to cache intermediate results and avoid redundant calculations.
**Time:** O(4^n * n) worst case, but often better in practice due to memoization · **Space:** O(n * 4^n) to store memoized results
**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
### Explanation
We can optimize the previous solution by caching intermediate results and pruning invalid paths early. We'll also handle overflow cases better.

```java
class Solution {
    private Map<String, List<String>> memo;
    
    public List<String> addOperators(String num, int target) {
        memo = new HashMap<>();
        return backtrackWithMemo(num, target, 0, num.length());
    }
    
    private List<String> backtrackWithMemo(String num, long target, int start, int len) {
        String key = start + "_" + target;
        if (memo.containsKey(key)) return memo.get(key);
        
        List<String> result = new ArrayList<>();
        
        // Base case: if we've used all digits
        if (start == len) {
            if (target == 0) result.add("");
            memo.put(key, result);
            return result;
        }
        
        // Handle leading zero case
        if (num.charAt(start) == '0') {
            List<String> next = backtrackWithMemo(num, target, start + 1, len);
            for (String expr : next) {
                result.add("0" + (expr.isEmpty() ? "" : "+" + expr));
            }
            memo.put(key, result);
            return result;
        }
        
        // Try different lengths of numbers starting at current position
        long curr = 0;
        for (int i = start; i < len; i++) {
            curr = curr * 10 + (num.charAt(i) - '0');
            if (curr > Integer.MAX_VALUE) break;
            
            List<String> next = backtrackWithMemo(num, target - curr, i + 1, len);
            for (String expr : next) {
                result.add(curr + (expr.isEmpty() ? "" : "+" + expr));
            }
        }
        
        memo.put(key, result);
        return result;
    }
}
```
### Algorithm
1. Use a hash map to store intermediate results
2. 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
3. Handle base cases and boundary conditions

# Solutions
### CSharp

```csharp
using 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 ; } }
```

### Java

```java
class 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 ); } } } }
```

### Python

```python
class 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 '''
```