How many distinct expressions are possible?

Question

I came across the following practice problem.

You are free to put any parentheses to the expression anywhere you want and as many as you want. However it should be a valid expression after you put the parentheses. The question is how many different numbers can you make? Ex. for 1 - 2 + 3 - 4 - 5 you can get six unique values as below:

1 - 2 + 3 - 4 - 5 = -7 

1 - (2 + 3) - 4 - 5 = -13

1 - (2 + 3 - 4) - 5 = -5

1 - (2 + 3 - 4 - 5) = 5

1 - 2 + 3 - (4 - 5) = 3

1 - (2 + 3) - (4 - 5) = -3

I can't seem to figure out how to have a Dynamic Programming formulation for the problem. I just started solving problems involving Dynamic Programming and can't seem to figure out how to approach this problem.

EDIT The range of numbers is 0<=N<=100 and length of expression (<=30)

Answer 1

Basic idea

The parentheses are basically interposed between numbers and operators, any imbalance can be fixed at the ends of the entire expression.

Possible placements of parentheses

A ( immediatetly before either operator is illegal syntax.

A ( immediately after a + is legal but pointless, since it doesn't change the order of evaluation. I'll assume we don't do this.

A ( immediately after a - is legal and important.

A ) immediately before a + is legal and important iff there was a matching ( before.

A ) immediately before a - is legal but pointless, since opening a new pair of parenthesis after the following number gives the same sign-change and more options later on, because we will have one more open pair we can close. I'll assume we don't do this either.

This means the only parentheses we actually need are opening parentheses before negative numbers and closing parentheses after positive ones. If we stick to those two, the sign the next number is multiplied with in the summation depends only on the number of open parentheses being even or odd.

This gives us the

Substructure

Parsing the state from left to right, after every number the present sub-problem can be represented as a set of pairs of

• the partial sum and
• the number of open parentheses.

Working out the specific example

Reading in +1:

(1, 0)

That is, there is only one solution for this sub-problem: The partial sum so far is 1 and the number of open parentheses is 0. From now on in each sub-problem I'll have one line for the pairs arising from every pair in the previous sub-problem.

Reading in -2:

(-1, 1), (-1, 0)

I.e. the partial sum is -1, but we may or may not have inserted an opening parenthesis.

Reading in +3:

(-4,1),(-4,0)

(2,0)

New in this sub-problem: We could optionally close a pair of parentheses, but only if one was open.

Reading in -4:

(0,2), (0,1)

(-8,0), (-8,1)

(-2,0), (-2,1)

Reading in -5:

(-5,2), (-5,3)

(5,1), (5,2)

(-13,0), (-13, 1)

(-3,1), (-3,2)

(-7,0), (-7,1)

(3,1), (3,2)

In the end we get the possible sums by looking only at the first element of each pair and discarding duplicates.