LeetCode 22 - Generate Parentheses

Question:

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

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

Answer:

The intuition behind generating valid combinations of parentheses for a given n is to use a recursive approach that explores all possible combinations while ensuring they are valid. Here's the intuition broken down:

Base Case: We start with n pairs of open and close parentheses. We want to generate combinations where every open parenthesis is eventually matched with a close parenthesis. So, the base case is when both the counts of open and close parentheses become zero, indicating that a valid combination has been found.

Recursive Approach: To generate valid combinations, we make recursive calls with two choices at each step:

If there are still available open parentheses (open count > 0), we can add an open parenthesis to the current combination and continue the recursion.

If the number of available close parentheses is greater than the number of available open parentheses (close count > open count), we can add a close parenthesis to the current combination and continue the recursion.

Backtracking: If at any point during the recursion, we encounter an invalid combination (e.g., more close parentheses than open parentheses), we backtrack by not making that particular recursive call. This ensures that only valid combinations are generated.

Exploration: The recursive approach explores all possible combinations by systematically adding open and close parentheses to the current combination. It explores different branching paths of recursion until it reaches the base case, at which point a valid combination is added to the result.

Approach

Initialization: The generateParenthesis method is called with the value of n, which represents the number of pairs of parentheses to generate. We initialize an empty list ans to store the valid combinations.

Recursive Helper Function: The real work is done in the generateValidParentheses method, which is a recursive helper function. It takes the following parameters:

open: The remaining count of open parentheses.

close: The remaining count of close parentheses.

current: A string representing the current combination of parentheses.

result: A list to store valid combinations.

Base Case: In the generateValidParentheses method, there is a base case check:

If both open and close are zero, it means that we have used all available open and close parentheses, and current contains a valid combination. We add current to the result list.

Recursive Calls:

If open is greater than zero, we make a recursive call with open - 1, indicating that we are using an open parenthesis, and we append an open parenthesis to the current string.

If close is greater than open, we make a recursive call with close - 1, indicating that we are using a close parenthesis, and we append a close parenthesis to the current string.

Backtracking: The recursive nature of this algorithm naturally explores all possible combinations of parentheses while ensuring that they are valid. If at any point in the recursion we encounter an invalid combination (e.g., more close parentheses than open parentheses), we backtrack by not making that particular recursive call.

Result: After the recursion completes, the ans list will contain all valid combinations of parentheses.

Example in main: In the main method, we demonstrate how to use the generateParenthesis method by creating an instance of the Solution class and calling it with an example value of n. The generated combinations are then printed to the console.

Time complexity:

In the generateParenthesis method, we call the generateValidParentheses method once, passing the initial values of n for open and close parentheses. The generateValidParentheses method is a recursive function.

In the generateValidParentheses method, for each recursive call, we either decrement the count of open parentheses (open) or the count of close parentheses (close) by 1. Since there are two recursive calls inside this method, the number of recursive calls made will be approximately 2^n.

Each recursive call performs constant work, such as appending characters to the current string and checking the base case.

Therefore, the overall time complexity is approximately O(2^n), where n is the number of pairs of parentheses.

Space complexity:

The primary space usage comes from the recursion stack. In the worst case, the maximum depth of the recursion is 2n because at each level, we either add an open or close parenthesis. Therefore, the space complexity due to the recursion stack is O(2n) = O(n).

Additionally, we have the current string, which can have a maximum length of 2n because it stores the current combination of parentheses. The space complexity for the current string is O(n).

The ans list stores all valid combinations. In the worst case, there can be 2^n valid combinations, each with a length of 2n. Therefore, the space complexity for the ans list is O(2^n * 2n) = O(4^n).

Code:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate_valid_parentheses(open_count, close_count, current, result):
            if open_count == 0 and close_count == 0:
                result.append(current)
                return

            if open_count > 0:
                generate_valid_parentheses(open_count - 1, close_count, current + '(', result)

            if close_count > open_count:
                generate_valid_parentheses(open_count, close_count - 1, current + ')', result)

        ans = []
        generate_valid_parentheses(n, n, '', ans)
        return ans