POTD Leet Code: 241. Different Ways to Add Parentheses in JS

To solve the problem of generating all possible ways to add parentheses to a mathematical expression (e.g., “2-1-1” or “23-45″), we need to consider how to evaluate expressions in multiple orders using recursive partitioning. Here’s a solution in JavaScript:

Problem:

Given a string containing numbers and operators (+, -, *), return all possible results from computing all the different possible ways to group numbers and operators.

Approach:

1. Recursive Partitioning: For each operator, partition the expression into left and right sides.
2. Recursive Evaluation: Recursively compute the result of the left and right subexpressions.
3. Combine: Combine the results from the left and right sides using the operator.

Solution Code:

function diffWaysToCompute(expression) {
    const results = [];

    // Base case: if the expression is a single number, return it as the only result
    if (!expression.match(/[\+\-\*]/)) {
        return [parseInt(expression)];
    }

    // Loop through each character in the expression
    for (let i = 0; i < expression.length; i++) {
        const char = expression[i];

        // If the character is an operator
        if (char === '+' || char === '-' || char === '*') {
            // Recursively compute the left and right side of the expression
            const leftResults = diffWaysToCompute(expression.slice(0, i));
            const rightResults = diffWaysToCompute(expression.slice(i + 1));

            // Combine the results from the left and right sides using the current operator
            for (const left of leftResults) {
                for (const right of rightResults) {
                    let result;
                    if (char === '+') {
                        result = left + right;
                    } else if (char === '-') {
                        result = left - right;
                    } else if (char === '*') {
                        result = left * right;
                    }
                    results.push(result);
                }
            }
        }
    }

    return results;
}

// Example usage:
const expression = "2*3-4*5";
console.log(diffWaysToCompute(expression)); // Output: [-34, -10, -14, -10, 10]

Explanation:

1. Base Case: If the expression contains no operators, it’s a number, and we return it.
2. Recursive Step: For each operator (+, -, *), split the expression into two parts: left and right.
3. Recursive Call: Recursively compute possible results for both parts.
4. Combine Results: After the recursive calls, we combine the results from the left and right parts using the operator.

Example:

For the input "2*3-4*5", the possible ways to compute it are:

• (2 * (3 - (4 * 5))) = -34
• ((2 * 3) - (4 * 5)) = -14
• And more combinations.

This solution uses recursion and divides the problem into subproblems, making it an efficient way to explore all valid groupings of parentheses.