Generate parentheses solution

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.

• At which line did you originally include the return statement? – dfhwze Jun 11 '19 at 19:10
• After the line build_parentheses.counter += 1 in the base-case if.... – EML Jun 11 '19 at 19:14
• The key difference is you are using an else: block here, rendering the returnobsolete. – dfhwze Jun 11 '19 at 19:24
• No, but because all remaining code in the function is in the else, there is no more reachable code detected. If you have more questions about the scope of code blocks, take it to chat :) – dfhwze Jun 11 '19 at 19:28
• – dfhwze Jun 11 '19 at 19:30

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
}

• in the second snippet I would say the else is unnecessary. It allows you to arrange the rest of the code with 1 less level of indentation – Maarten Fabré Jun 12 '19 at 7:46
• @MaartenFabré You are correct. But these snippets are just trivial examples to show the purpose of the return statement. – dfhwze Jun 12 '19 at 8:01

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).

• I would skip the auxiliary function, and make 0 the default arguments for open_count and closed_count – Maarten Fabré Jun 12 '19 at 7:48
• Thank yo for this reply :) – EML Jun 12 '19 at 9:00
• @EML You're welcome! @Maarten Fabré I don't agree; open_count and closed_count aren't a part of the public API, so they shouldn't be in the API function – Quelklef Jun 12 '19 at 15:37

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.