Here is solutions for Generate Parentheses.

1. Understand the problem

• Given an integer n, generate all combinations of n pairs of parentheses that are valid (well-formed).

Example:

n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"] (order can differ)

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. What is the range of n?

• In LeetCode, 1 <= n <= 8 is typical. We’ll assume n is small (like ≤ 10), so exponential solutions are acceptable.

1. Do we care about the order of the output list?

• No specific order is required. Any order that contains all valid combinations is acceptable.

1. Are there any invalid inputs like n <= 0?

• Usually constraints exclude them, but if n = 0, a reasonable answer is [””] (one empty string). For this problem we’ll focus on n >= 1.

1. Can we use extra space / recursion?

• Yes. This is a classic backtracking problem; recursion + extra lists are fine.

1. Is there any requirement about duplicates?

• No; duplicates won’t appear if we build strings in a structured way (like backtracking). If we use brute force, we must be careful not to generate duplicates, but usually we won’t.

3. Explore examples.

1. Example 1: n = 1

All strings of length 2:

() → valid
Answer: ["()"]

1. Example 2: n = 2

Answer: ["(())", "()()"]

1. Example 3: n = 3

- ((()))

- (()())

- (())()

- ()(())

- ()()()

1. Example 4: n = 0

Just empty string: [""]

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Naive Brute Force (Generate All Strings and Filter) - Time O(2^(2N) * N), Space O(2^(2N) * N)

• All strings of length 2n made from ‘(‘ and ‘)’ are 2^(2n) possibilities.

• For each string:

  • Check if it’s a valid parentheses string.

  • If valid, add to result.

• Validity check:

  • ’(‘ → balance += 1

  • ’)’ → balance -= 1

  • If balance < 0 → invalid (more ‘)’ than ‘(‘ somewhere).

4.2. Backtracking with Counts (Optimal / Standard) - Time O(4^n / (n^(3/2)) * N), Space O(4^n / (n^(3/2)) * N)

Key Idea:

- Build the string only along valid paths:

Track:

- open_used: how many '(' used so far.

- close_used: how many ')' used so far.

Rules:

- We can always add '(' if open_used < n.

- We can add ')' only if close_used < open_used. (we can’t close more than we opened)

4.3. DP / Catalan (Conceptual)

S = "(" + A + ")" + B

• A is some valid string with i pairs.

• B is some valid string with n - 1 - i pairs.

• For all i from 0 to n-1, combine all A in dp[i] with all B in dp[n-1-i].

5. Implement solutions.

5.1. Naive Solution - Time O(2^2n * n), Space O(2^2n * n)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def valid(s: str):
            open = 0
            for c in s:
                open += 1 if c == '(' else -1
                if open < 0:
                    return False
            return not open

        def dfs(s: str):
            if n * 2 == len(s):
                if valid(s):
                    res.append(s)
                return

            dfs(s + '(')
            dfs(s + ')')

        dfs("")
        return res

• Time: O(2^2n * n)

• Space: O(2^2n * n)

5.2. Backtracking with Prunning - Time O(4^N/sqrt(n)), Space O(N)

Idea:

• Backtrack ‘)’ after ‘(‘

• Prunning invalid cases.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        stack = []
        res = []

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return

            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res

• Time: O(4^N/sqrt(n))

• Space: O(N)

5.3. Dynamic Programming - Time O(4^N/sqrt(n)), Space O(N)

class Solution:
    def generateParenthesis(self, n):
        res = [[] for _ in range(n+1)]
        res[0] = [""]

        for k in range(n + 1):
            for i in range(k):
                for left in res[i]:
                    for right in res[k-i-1]:
                        res[k].append("(" + left + ")" + right)

        return res[-1]

• Time: O(4^N/sqrt(n))

• Space: O(N)

6. Dry run testcases.

Example 1: n = 3

Backtrack to “((“ and Try ‘)’: