Generate parenthesis

The algorithm is called recursively. At every call it returns the list of every possible arrangement of parenthesis based on what has already been generated.

1) Call the algorithm from an empty string, set the number of opened and closed parenthesis to 0

2) At each call we can either open a parenthesis and increment the corresponding variable or close a parenthesis and increment the corresponding variable. The rules to follow are these:

a) The number of closed parenthesis is always smaller or equal to the number of opened parenthesis

b) The number of opened and closed parenthesis can not be greater than the total number of parenthesis

3) Call recursively the algorithm on the updated variables

4) Once the number of opened and closed parenthesis are both equal to the total number of parenthesis, just return the obtained string

5) Going back to the top concatenate the list of generated parenthesis

6) Return the total list

def generateParenthesis(self, n: int) -> List[str]:
    def helper(current_string, number_open, number_close, n):
        # if all parenthesis are opened and closed then nothing to do, return the current string
        if number_open == n and number_close == n:
            return([current_string])
        # if every parenthesis are already opened we only need to close them
        elif number_open == n:
            return(helper(current_string + ")", number_open, number_close+1, n))
        # if the same number of parenthesis are opened and closed we can't close a new one and need to open one
        elif number_open == number_close:
            return(helper(current_string + "(", number_open+1, number_close, n))
        # otherwise we can open a new parenthesis or close an opened parenthesis
        else:
            return(helper(current_string + "(", number_open+1, number_close, n) +
                   helper(current_string + ")", number_open, number_close+1, n))
    
    return(helper("", 0, 0, n))