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, "")

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.