Different Ways to Add Parentheses

Problem

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]


Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

Solution

Left and Right Recursive Solution

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                String left = input.substring(0, i), right = input.substring(i + 1);
                List<Integer> leftRes = diffWaysToCompute(left), rightRes = diffWaysToCompute(right);
                for (int num1 : leftRes) {
                    for (int num2 : rightRes) {
                        if (ch == '+') res.add(num1 + num2);
                        else if (ch == '-') res.add(num1 - num2);
                        else if (ch == '*') res.add(num1 * num2);
                    }
                }
            }
        }
        if (res.size() == 0) res.add(Integer.parseInt(input)); //Last recursion returns 
        return res;
    }
}

Optimal Solution of Above Using Map

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        return helper(input, new HashMap<>());
    }

    private List<Integer> helper(String input, Map<String, List<Integer>> map) {
        if (map.containsKey(input)) return map.get(input);

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                String left = input.substring(0, i), right = input.substring(i + 1);
                List<Integer> leftRes = diffWaysToCompute(left), rightRes = diffWaysToCompute(right);
                for (int num1 : leftRes) {
                    for (int num2 : rightRes) {
                        if (ch == '+') res.add(num1 + num2);
                        else if (ch == '-') res.add(num1 - num2);
                        else if (ch == '*') res.add(num1 * num2);
                    }
                }
            }
        }
        if (res.size() == 0) res.add(Integer.parseInt(input));
        map.put(input, res);
        return res;
    }
}

Analysis

To get different result, we need to think about the sequence of calculating the operations
Then it becomes a permutation of sequences of calculating the operations
To get all possibles, we have a for loop from 0 until the end of input
If we have an operation char at current index, we need its left and right operands
We construct them by recursively calling the method with input.substring(0, i) and input.substring(i + 1)
Then we collect different result using two nested for loops calculating value based on the operator
At the end of recursion, we will have only number value hence we simply parse and add it to our res
Notice that we can use a HashMap to optimize our recursion's calls