Expression Add Operators

HARD

Description

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

Checkout 2 different approaches to solve Expression Add Operators. Click on different approaches to view the approach and algorithm in detail.

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.

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

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 Analysis

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

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Expression Add Operators. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Expression Add Operators

Patterns:

MathBacktracking

Data Structures:

String

Companies:

Pinterest |