Generate parentheses solution

Question

I have coded a solution to build all valid permutations of parentheses.

My code is below.

I have a question on my code based on a comment by my PEP8 checker. It said that there was no need to include the line return anywhere in the code (initially I included one). The solution works but I have never had a case using recursion where I didn't have to use the return line in the base-case.

How come I don't need it here?

The following expression initially had a return statement but I was told this was obsolete.

    if number_open == number_pairs and number_closed == number_pairs:
        print(output)
        build_parentheses.counter += 1
        return

Python 3.7 code:

"""Module builds all valid permutations of n parentheses
For example: n = 3:
    ((()))
    (()())
    (())()
    ()(())
    ()()()
Total = 5
"""


def build_parentheses(number_pairs: int,
                      output="",
                      number_open=0,
                      number_closed=0)-> str:
    """The function that builds the parentheses. Output as a string:
        number_pairs: number of parentheses pairs user desired
        All other parameters are private
    """
    if number_open == number_pairs and number_closed == number_pairs:
        print(output)
        build_parentheses.counter += 1
    else:
        if number_open < number_pairs:
            output += "("
            build_parentheses(number_pairs, output, number_open + 1, number_closed)
            output = output[:-1]
        if number_closed < number_open and number_open:
            output += ")"
            build_parentheses(number_pairs, output, number_open, number_closed + 1)


if __name__ == "__main__":
    build_parentheses.counter = 0
    build_parentheses(5)
    print(f"=========\n{build_parentheses.counter} solutions")

By comparison, in this post I made, I did use the return statement.

Answer 1

As mentioned here I'll provide a short answer to summarize what we discussed. A return statement only impacts code that short-circuits any remaining code that would have been called if omitted.

pseudo code snippets below

The return statement here skips snippet 2.

if (condition) {
  // .. snippet 1
  return;
}
// snippet 2

The return statement here is unnecessary.

if (condition) {
  // .. snippet 1
  return;
} else {
  // snippet 2
}

Answer 2

Effects

This is my main complaint about your code. build_parentheses prints out its results, but it would be cleaner for it to return them as a list, or yield them.

.counter

Using the attribute build_parenthesis.counter like this is technically fine, but it's really strange. I don't feel that ad-hoc attributes are particularly Pythonic, especially for functions. Also, .counter will not be needed if build_parentheses returns a list as suggested.

Names

I'd recommend X_count rather than number_X. It's mostly preference, though.

Public API

Since the number_open and number_closed parameters are not part of the public API, I'd recommend removing them. Make build_parentheses take only one parameter, number_pairs. It will call, and return the results of, build_parentheses_aux, an auxiliary/helper function, which takes number_pairs as well as several private/internal parameters.

Chained comparisons

number_open == number_pairs and number_closed == number_pairs may be written as number_open == number_closed == number_pairs. Generally, Python interprets chained comparisons as if they were combined with and. Two comparisons A and B applied to three variables x, y, and z like x A y B z is the same as writing x A y and y B z.

Everything else looks good

Style is generally good, though a space to the left of -> str would be nice; and number_open rather than and number_open != 0 is Pythonic; if __name__ == "__main__" guard is good; snake_case is good; you have a docstring, ...

Suggested Code

Here is your code, with all suggestions implemented:

def build_parentheses(pair_count: int) -> str:
    """The function that builds the parentheses. Output as a string:
        pair_count: number of parentheses pairs user desired
    """
    return build_parentheses_aux(pair_count, 0, 0)

def build_parentheses_aux(pair_count: int,
                      open_count,
                      closed_count)-> str:
    """Auxiliary build_parentheses function.
        pair_count: number of parentheses pairs
        open_count: number of open parens so far
        closed_count: number of closed parens so far
    """
    if open_count == closed_count == pair_count:
        return [""]
    else:
        result = []
        if open_count < pair_count:
            for r in build_parentheses_aux(pair_count, open_count + 1, closed_count):
                result.append("(" + r)
        if closed_count < open_count and open_count:
            for r in build_parentheses_aux(pair_count, open_count, closed_count + 1):
                result.append(")" + r)
        return result

if __name__ == "__main__":
    options = build_parentheses(5)
    print("\n".join(options) + f"\n=========\n{len(options)} solutions")

If you are familiar with generators, you could also write build_parentheses_aux as a generator, which would look cleaner (but may be less efficient).

Answer 3

There is no need for a return statement here because when you reach the end of a function, there is an implicit return.

For example:

1 def exampleFunction():
2   if someCondition:
3     doThis()
4   else:
5     doTheOtherThing()
6

We could put a return statement after the call to doThis(), but this would make no difference to the execution of the code. When someCondition is True, we enter that code block and then call doThis(). Then, we go to line 6 and implicitly return from the function.

So after executing line 3, we jump to line 6 and implicitly return, so explicitly returning after line 3 makes no difference.