Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example:

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Your function should satisfy the following constraints:

• 1 <= n <= 8

Explain your approach, provide code with comments, and analyze the time and space complexity of your solution.

def generateParenthesis(n):
    """
    Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

    For example, given n = 3, the function should return: ["((()))", "(()())", "(())()", "()(())", "()()()"]
    """
    result = []
    
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            result.append(s)
            return
        
        if open_count < n:
            backtrack(s + "(", open_count + 1, close_count)
        
        if close_count < open_count:
            backtrack(s + ")", open_count, close_count + 1)
            
    backtrack("", 0, 0)
    return result

# Example usage:
n = 3
print(generateParenthesis(n)) # Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

n = 1
print(generateParenthesis(n)) # Output: ['()']

Explanation:

1. generateParenthesis(n) Function:

   • Initializes an empty list result to store the valid parenthesis combinations.
   • Calls the backtrack helper function to generate the combinations recursively.
   • Returns the result list.

2. backtrack(s, open_count, close_count) Function (Recursive):

   • Base Case: If the length of the current string s is equal to 2 * n (meaning we have used all n pairs of parentheses), we add s to the result list and return.
   • Recursive Steps:
     • If the number of open parentheses used so far (open_count) is less than n, we can add an open parenthesis '(' to the string s. We then recursively call backtrack with the updated string s + '(', an incremented open_count, and the same close_count. This explores adding another open parenthesis.
     • If the number of close parentheses used so far (close_count) is less than the number of open parentheses used (open_count), we can add a close parenthesis ')' to the string s. We then recursively call backtrack with the updated string s + ')', the same open_count, and an incremented close_count. This explores adding a close parenthesis, but only if it maintains the well-formed property (i.e., we don't have more closing than opening parentheses).

Example Walkthrough (n = 2):

1. backtrack("", 0, 0)
2. backtrack("(", 1, 0)
3. backtrack("((", 2, 0)
4. backtrack("(()", 2, 1)
5. backtrack("(())", 2, 2) -> result.append("(())")
6. Backtrack to backtrack("((", 2, 0)
7. Backtrack to backtrack("(", 1, 0)
8. backtrack("()", 1, 1)
9. backtrack("()(", 2, 1)
10. backtrack("()()", 2, 2) -> result.append("()()")

Time and Space Complexity

Time Complexity: O(4ⁿ / √n). This is due to the Catalan number, which represents the number of possible valid parenthesis combinations. In each recursive call, we have two choices: add '(' or ')'. The number of nodes in the recursion tree corresponds to the nth Catalan number, which grows exponentially.

Space Complexity: O(n). The space complexity is dominated by the depth of the recursion, which can go up to 2n in the worst case. Also, storing the valid combinations in the result list will take up space, but that's considered output space.