282. Expression Add Operators – Leetcode Solutions

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.

from typing import List

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        # Helper function for recursive backtracking
        def backtrack(index: int, prev_operand: int, current_operand: int, value: int, expression: List[str]):
            # Base case: If we have reached the end of the string
            if index == len(num):
                # If the final value is equal to the target and current_operand is zero
                if value == target and current_operand == 0:
                    # Join the expression list into a string and add it to results
                    results.append("".join(expression[1:]))  # Skip the first operator which is always ''
                return
            
            # Start building the current operand
            for i in range(index, len(num)):
                # If the number has leading zeros, we skip the loop
                if i != index and num[index] == '0':
                    break
                
                # Extract the next portion of the string as an integer
                current_str = num[index:i+1]
                current_val = int(current_str)

                # Backtracking: Add the current operand to the expression with '+' operator
                backtrack(i + 1, current_val, 0, value + current_val, expression + ['+', current_str])
                
                # If not at the start, we can add the '-' and '*' operators as well
                if index > 0:
                    backtrack(i + 1, -current_val, 0, value - current_val, expression + ['-', current_str])
                    backtrack(i + 1, prev_operand * current_val, 0, value - prev_operand + (prev_operand * current_val), expression + ['*', current_str])
        
        results = []
        backtrack(0, 0, 0, 0, [])
        return results

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    // Main function to generate all valid expressions
    vector<string> addOperators(string num, int target) {
        vector<string> results; // To store the final valid expressions
        string expression;      // To build the current expression
        backtrack(num, target, 0, 0, 0, expression, results); // Start backtracking
        return results;
    }
    
private:
    // Helper function for recursive backtracking
    void backtrack(const string& num, int target, int index, long prev_operand, long current_value, string& expression, vector<string>& results) {
        // Base case: if we've processed the entire string
        if (index == num.size()) {
            // If the current expression evaluates to the target, add it to the results
            if (current_value == target) {
                results.push_back(expression);
            }
            return;
        }

        // Temporary string to hold the current operand
        string current_operand_str;
        long current_operand = 0;

        // Loop through the remaining digits to build the next operand
        for (int i = index; i < num.size(); ++i) {
            // Edge case: if the number starts with '0', we can only use '0' as an operand
            if (i > index && num[index] == '0') {
                break;
            }

            // Append the current digit to the operand string
            current_operand_str += num[i];
            // Convert the current operand string to a number
            current_operand = current_operand * 10 + (num[i] - '0');

            // If this is the first operand, just initialize the expression without any operators
            if (index == 0) {
                expression += current_operand_str; // Add the operand
                backtrack(num, target, i + 1, current_operand, current_operand, expression, results);
                expression.erase(expression.size() - current_operand_str.size()); // Backtrack: remove the operand
            } else {
                // Try adding a '+' operator before the current operand
                expression += '+' + current_operand_str;
                backtrack(num, target, i + 1, current_operand, current_value + current_operand, expression, results);
                expression.erase(expression.size() - current_operand_str.size() - 1); // Backtrack

                // Try adding a '-' operator before the current operand
                expression += '-' + current_operand_str;
                backtrack(num, target, i + 1, -current_operand, current_value - current_operand, expression, results);
                expression.erase(expression.size() - current_operand_str.size() - 1); // Backtrack

                // Try adding a '*' operator before the current operand
                expression += '*' + current_operand_str;
                backtrack(num, target, i + 1, prev_operand * current_operand, 
                          current_value - prev_operand + (prev_operand * current_operand), 
                          expression, results);
                expression.erase(expression.size() - current_operand_str.size() - 1); // Backtrack
            }
        }
    }
};

var addOperators = function(num, target) {
    // To store all valid expressions
    const results = [];
    
    // Helper function for recursive backtracking
    const backtrack = (index, prevOperand, currentValue, expression) => {
        // Base case: If we have reached the end of the string
        if (index === num.length) {
            // If the current expression evaluates to the target, add it to results
            if (currentValue === target) {
                results.push(expression);
            }
            return;
        }

        // Temporary string to hold the current operand
        let currentOperandStr = '';
        let currentOperand = 0;

        // Iterate over the remaining characters in the string
        for (let i = index; i < num.length; i++) {
            // Skip if the number has leading zeros
            if (i > index && num[index] === '0') break;

            // Build the current operand from the string
            currentOperandStr += num[i];
            currentOperand = currentOperand * 10 + (num[i] - '0');

            // If this is the first operand, don't add an operator before it
            if (index === 0) {
                backtrack(i + 1, currentOperand, currentOperand, currentOperandStr);
            } else {
                // Add '+' operator and recurse
                backtrack(i + 1, currentOperand, currentValue + currentOperand, expression + '+' + currentOperandStr);
                
                // Add '-' operator and recurse
                backtrack(i + 1, -currentOperand, currentValue - currentOperand, expression + '-' + currentOperandStr);
                
                // Add '*' operator and recurse (handle precedence properly)
                backtrack(i + 1, prevOperand * currentOperand, currentValue - prevOperand + (prevOperand * currentOperand), expression + '*' + currentOperandStr);
            }
        }
    };
    
    // Start backtracking from the first character
    backtrack(0, 0, 0, '');
    
    // Return all the valid expressions
    return results;
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> addOperators(String num, int target) {
        // To store all valid expressions
        List<String> results = new ArrayList<>();
        
        // Start the recursive backtracking
        backtrack(num, target, 0, 0, 0, "", results);
        
        // Return the list of valid expressions
        return results;
    }
    
    /**
     * Helper function for recursive backtracking
     * @param num The input string of digits
     * @param target The target value
     * @param index The current position in the string
     * @param prevOperand The previous operand used (for handling multiplication)
     * @param currentValue The current value of the expression being evaluated
     * @param expression The current expression being built
     * @param results The list of valid expressions
     */
    private void backtrack(String num, int target, int index, long prevOperand, long currentValue, String expression, List<String> results) {
        // Base case: If we have processed the entire string
        if (index == num.length()) {
            // If the current expression evaluates to the target, add it to results
            if (currentValue == target) {
                results.add(expression);
            }
            return;
        }
        
        // To build the current operand from the string
        long currentOperand = 0;
        String currentOperandStr = "";
        
        // Iterate through the remaining characters of the string
        for (int i = index; i < num.length(); i++) {
            // If the number starts with '0', we should break to avoid leading zeros
            if (i > index && num.charAt(index) == '0') {
                break;
            }
            
            // Append the current character to the operand string
            currentOperandStr += num.charAt(i);
            // Convert the current operand string to a number
            currentOperand = currentOperand * 10 + (num.charAt(i) - '0');
            
            // If this is the first operand, do not add an operator before it
            if (index == 0) {
                // Pass the current operand without any operator
                backtrack(num, target, i + 1, currentOperand, currentOperand, currentOperandStr, results);
            } else {
                // Try adding a '+' operator
                backtrack(num, target, i + 1, currentOperand, currentValue + currentOperand, expression + "+" + currentOperandStr, results);
                
                // Try adding a '-' operator
                backtrack(num, target, i + 1, -currentOperand, currentValue - currentOperand, expression + "-" + currentOperandStr, results);
                
                // Try adding a '*' operator (handling multiplication precedence)
                backtrack(num, target, i + 1, prevOperand * currentOperand, 
                          currentValue - prevOperand + (prevOperand * currentOperand), 
                          expression + "*" + currentOperandStr, results);
            }
        }
    }
}