Introduction

In this blog post, we will explore how to solve the LeetCode problem "22" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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: ["()"] Constraints: 1 <= n <= 8

Explanation

Here's the breakdown of the solution:

• Backtracking Approach: The core idea is to use backtracking. We build the strings recursively, adding either a left or right parenthesis at each step, as long as it maintains the validity of the parenthesis string (number of open parens >= number of closed parens, and we don't exceed the allowed number of open/close parens).
• Maintaining Open and Close Counts: We keep track of the number of open and close parentheses used so far. This allows us to efficiently determine if adding a parenthesis will lead to a valid string.

• Base Case: When the number of open and close parentheses both equal n, we've constructed a valid string, and we add it to our results.

• Time and Space Complexity: O(4ⁿ / √n), which is the nth Catalan number, as there can be at most that many valid combinations. Space complexity is O(n) due to the depth of the recursion stack, where n is the input.

Code

    def generateParenthesis(n: int) -> list[str]:
    """
    Generates all combinations of well-formed parentheses.

    Args:
        n: The number of pairs of parentheses.

    Returns:
        A list of strings representing all valid combinations.
    """

    result = []

    def backtrack(s: str, open_count: int, close_count: int):
        """
        Recursive helper function to build the parenthesis strings.

        Args:
            s: The current string being built.
            open_count: The number of open parentheses used so far.
            close_count: The number of close parentheses used so far.
        """
        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