Expression Add Operators

91.Expression Add Operators

String

Backtracking

Problem Statement:

Given a string of digits num and a target integer target, return all valid expressions that can be formed by inserting the operators +, -, and * between the digits in num so that the expression evaluates to target.

Algorithm:

1. Use a backtracking approach to generate all valid expressions.
2. For each substring of the input string:
• If it's the first number in the expression, add it directly to the current path.
• Otherwise, try appending each of the three operators (+, -, *) to the current path and recursively evaluate the expression.
3. Keep track of the current evaluated value (eval) and the last operand (multed) to handle multiplication correctly.
4. Ignore numbers with leading zeros.
5. Add valid expressions to the result list if they evaluate to the target.

Complexity:

Time: O(4^n), where n is the length of the input string | Space: O(n) for recursion depth.

Java Implementation:

import java.util.*;

public class Solution {
    public List addOperators(String num, int target) {
        // Result list to store all valid expressions that evaluate to the target
        List result = new ArrayList<>();

        // Start the recursive backtracking process
        backtrack("", num, target, 0, result, 0L, 0L);

        // Return the list of valid expressions
        return result;
    }

    private void backtrack(String path, String num, int target, int start, List result, long eval, long multed) {
        // Base case: if we've processed all characters in the num string
        if (start == num.length()) {
            // Check if the evaluated value matches the target
            if (target == eval) {
                // If so, add the current expression (path) to the result
                result.add(path);
            }
            return; // End the current recursion branch
        }

        // Try to form numbers using substrings starting at the 'start' index
        for (int i = start; i < num.length(); i++) {
            // Extract the current number from the substring [start, i + 1]
            long curr = Long.parseLong(num.substring(start, i + 1));

            // Edge case: Avoid numbers with leading zeros, e.g., "05"
            if (num.charAt(start) == '0' && i != start) {
                break; // Stop processing further substrings if a leading zero is encountered
            }

            // If we're at the beginning of the expression, we can't add an operator
            // Just add the number to the path and move forward
            if (start == 0) {
                backtrack(path + curr, num, target, i + 1, result, curr, curr);
            } else {
                // Try adding a '+' operator
                backtrack(path + '+' + curr, num, target, i + 1, result, eval + curr, curr);

                // Try adding a '-' operator
                backtrack(path + '-' + curr, num, target, i + 1, result, eval - curr, -curr);

                // Try adding a '*' operator
                // Note: Multiplication requires adjusting the eval value. We "undo" the effect of the last number
                // in the evaluation (multed) and replace it with the result of the multiplication.
                backtrack(path + '*' + curr, num, target, i + 1, result, eval - multed + multed * curr, multed * curr);
            }
        }
    }
}

Python Implementation:

class Solution:
    def addOperators(self, num: str, target: int):
        result = []
        self.backtrack("", num, target, 0, 0, 0, result)
        return result

    def backtrack(self, path, num, target, start, eval, multed, result):
        if start == len(num):
            if eval == target:
                result.append(path)
            return

        for i in range(start, len(num)):
            curr = int(num[start:i + 1])
            if num[start] == '0' and i != start:
                break

            if start == 0:
                self.backtrack(path + str(curr), num, target, i + 1, curr, curr, result)
            else:
                self.backtrack(path + '+' + str(curr), num, target, i + 1, eval + curr, curr, result)
                self.backtrack(path + '-' + str(curr), num, target, i + 1, eval - curr, -curr, result)
                self.backtrack(path + '*' + str(curr), num, target, i + 1, eval - multed + multed * curr, multed * curr, result)

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    vector addOperators(string num, int target) {
        vector result;
        backtrack("", num, target, 0, 0, 0, result);
        return result;
    }

private:
    void backtrack(string path, string num, int target, int start, long eval, long multed, vector& result) {
        if (start == num.size()) {
            if (eval == target) {
                result.push_back(path);
            }
            return;
        }

        for (int i = start; i < num.size(); i++) {
            string currStr = num.substr(start, i - start + 1);
            long curr = stol(currStr);
            if (num[start] == '0' && i != start) break;

            if (start == 0) {
                backtrack(path + currStr, num, target, i + 1, curr, curr, result);
            } else {
                backtrack(path + "+" + currStr, num, target, i + 1, eval + curr, curr, result);
                backtrack(path + "-" + currStr, num, target, i + 1, eval - curr, -curr, result);
                backtrack(path + "*" + currStr, num, target, i + 1, eval - multed + multed * curr, multed * curr, result);
            }
        }
    }
};