Generate Parentheses medium

Problem Statement

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: ["()"]

Steps

The problem can be solved using backtracking. The key idea is to maintain a count of open and closed parentheses.

1. Base Case: If the number of open parentheses equals n and the number of closed parentheses equals n, we have a valid combination. Add it to the result list.

2. Recursive Step:

   • If the number of open parentheses is less than n, we can add an opening parenthesis. Recursively call the function with one more open parenthesis.
   • If the number of closed parentheses is less than the number of open parentheses, we can add a closing parenthesis. Recursively call the function with one more closed parenthesis.

3. Backtracking: After each recursive call, we need to remove the last added parenthesis (backtracking) to explore other possibilities.

Explanation

The backtracking approach systematically explores all possible combinations of parentheses. By keeping track of open and closed parentheses, we ensure that we only generate valid combinations. The algorithm avoids invalid combinations by only allowing a closing parenthesis if there's a matching open parenthesis available.

Code

def generateParenthesis(n):
    """
    Generates all combinations of well-formed parentheses.

    Args:
        n: The number of pairs of parentheses.

    Returns:
        A list of strings, where each string represents a valid combination of parentheses.
    """
    result = []
    
    def backtrack(s='', open_count=0, close_count=0):
        if open_count == n and close_count == 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()
    return result

Complexity

• Time Complexity: O(4ⁿ / n^1.5). This is because the number of valid combinations is given by the Catalan number, which has this asymptotic growth. The backtracking algorithm explores all possibilities, but many are pruned due to invalid combinations.
• Space Complexity: O(4ⁿ / n^1.5) in the worst case to store the result list. The recursive call stack can also take up space, but it's proportional to n in the worst-case scenario (deepest recursion). The space complexity is dominated by the result list.