Expression Add Operators
HardPrompt
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 <= 10numconsists of only digits.-231 <= target <= 231 - 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:
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); } } }}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
Solutions
Solution
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 ; } }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.