# Generate all valid combinations of n pair of parentheses

Implement an algorithm to print all valid (e.g. properly opened and closed) combinations of n pair of parentheses.

Following is my implementation and I think it works. Is the algorithm efficient? Do you see any coding issues?

def compute_all_parens (n, left, right, s):
if right == n:
print (s)
return
if left < n:
compute_all_parens(n, left+1, right, s + "(")
if right < left:
compute_all_parens(n, left, right+1, s + ")")

# call syntax: compute_all_parens(5, 0, 0, "")

• As with any recursive algorithm, stack depth (excessive nesting) could become an issue. All recursive algorithms can be rewritten without recursion, so, if you plan to use this with large n, you might want to do that. However, I find your implementation very clever in terms of code purity. – Barry Carter Sep 30 '17 at 14:59
• @BarryCarter: The number of valid strings formed from n pairs of parentheses is equal to C_n, the nth Catalan number, which grows exponentially with n; it is approximately 4^n. If you provide an n large enough that this implementation blows the stack, the algorithm would never have finished, anyway. – wchargin Sep 30 '17 at 19:30

### API

The compute_all_parens function requires 4 parameters. From a user's perspective, it would be more natural to require only one, to avoid confusion about what values to pass for the others. You could use an inner function to encapsulate your implementation details:

def print_all_parens(n):
def print_parens(left, right, s):
if right == n:
print(s)
return
if left < n:
print_parens(left + 1, right, s + "(")
if right < left:
print_parens(left, right + 1, s + ")")

print_parens(0, 0, "")


I also corrected some formatting issues, following PEP8.

### Use generators

Instead of printing, it would be nicer to return a generator:

def compute_all_parens(n):
def compute_parens(left, right, s):
if right == n:
yield s
return
if left < n:
yield from compute_parens(left + 1, right, s + "(")
if right < left:
yield from compute_parens(left, right + 1, s + ")")

yield from compute_parens(0, 0, "")


This will give callers the freedom to do whatever they want with the combinations.

It's fine, but there are some small issues with it.

1. You call your function compute_all_parens, yet it does not return anything. It prints all parentheses, therefore the name print_all_parens would be more appropriate.
2. The names left and right are only somewhat descriptive. The name s is completely nondescript. Naming is hard, but as long as you provide that interface to the user, you either need better names or a documentation string.
3. It provides an unintuitive user interface that's prone to errors. You could add another function that takes care of that:

def print_parens(number_of_parens):
"""Prints all valid variants with number_of_parens parentheses.

Examples:

>>> print_parens(1)
()

>>> print_parens(2)
(())
()()

>>> print_parens(3)
((()))
(()())
(())()
()(())
()()()
"""
print_all_parens(number_of_parens, 0, 0, "")


You can hide your original function as a closure in there, but I'm not sure whether that counts as best practice.

• Shouldn't print_parens(3) print (())() as well? – 409_Conflict Sep 30 '17 at 12:18
• @MathiasEttinger yes it should. Added. – Zeta Sep 30 '17 at 22:54