Book of programming problems

Complexity (1-100): 20

Make all possible combinations of  parenthesis placement in a product of  n letter multipliers: a,b,c,.... All multipliers should be embraced in parenthesis. For example,  '(a*b)*(c*d)*(e*f)' is incorrect placement, because multipliers (a*b) and (c*d) are not embraced in parenthesis. The correct answeer might be the following: '((a*b)*(c*d))*(e*f)'. Double paranthesis and paranthesis around one letter are not permitted, such as in  '((a*b))' and '(a)*b'. Paranthesis around the whole product are not permitted, such as in '((a*b)*c)'.
Example: for n=3, the correct answer is a set of two formulas: a*(b*c) and (a*b)*c.
For n=4, the answer is

a*(b*(c*d))
a*((b*c)*d)
(a*b)*(c*d)
(a*(b*c))*d
((a*b)*c)*d

Is is plain to see that each of the resulting formulas should be in the form of the product:


Therefore the resulting set of formulas can be constructed be recursively dividing the problem into to two subproblems, for the left-hand and the right-hand multipliers. For n variables there is n-1 ways to divide them into two sequential groups. The algorithm consists of a recursive function formula(firstLetter,lastLetter), which returns the list of all possible formulas over variables from firstLetter to lastLetter, inclusively. It recursively calls itself to construct two sets of formulas:  formula(a₁,...,a_k) and formula(a_k+1,...,a_n). It than computes the cartesian product of the sets by joining each formula from the first set with each formula from the second through the '*' operator.