LeetCode Q241: Different Ways to Add Parentheses

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:

Don/t be horrified by this question. It is not that hard, although I couldn't make it in the first place. Firstly, you should ignore parenthesis in this question, they are just things that are used to confusing you. The question indeed is all about grouping of numbers. 

The way numbers get grouped depends on where you separate the expression which is done by locating punctuation sign. Another thing is the minimal number of numbers in each group is TWO not ONE. 

So,  we start from expression with only two numbers, which has only one way of grouping. Let indicate this by a function f(n), where n is the number of numbers in a expression.

f(2) = 1, 

f(3) = 2, 

f(4) = f(3) + f(3) +f(2)  = 5

f(5) = f(4) + f(4) + f(2)*f(3) + f(3)*f(2)  = 14

f(6) = f(5) + f(4)*f(2) + f(3)*f(3) + f(2)*f(4) +f(5)= 42

.

.

.

f(n) = f(n-1) + f(n-2)*f(2) + f(n-3)*f(3) + ... + f(2)*f(n-3)

So, you see the pattern. Then, we basically, could use recursion to solve it. You also could use DP to save intermediate results.