Problem Description

You need to generate all valid combinations of parentheses given n pairs.

A valid combination means:

• Every opening parenthesis ( has a corresponding closing parenthesis )
• At any point while reading from left to right, the number of closing parentheses never exceeds the number of opening parentheses

For example:

• If n = 1, the only valid combination is "()"
• If n = 2, valid combinations are "(())" and "()()"
• If n = 3, valid combinations include "((()))", "(()())", "(())()", "()(())", and "()()()"

The solution uses a depth-first search approach with pruning. It tracks:

• l: count of left parentheses added so far
• r: count of right parentheses added so far
• t: the current string being built

The key insights for pruning invalid paths:

• Never add more than n left or right parentheses (l > n or r > n)
• Never have more right parentheses than left parentheses at any point (l < r)
• When both l and r equal n, we have a valid combination

The algorithm recursively tries adding a left parenthesis dfs(l + 1, r, t + '(') or a right parenthesis dfs(l, r + 1, t + ')'), building all valid combinations through this exploration.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem doesn't involve nodes and edges or graph traversal. We're generating combinations of parentheses, not working with a graph structure.

Need to solve for kth smallest/largest?

• No: We're not looking for the kth smallest or largest element. We need to generate ALL valid combinations.

Involves Linked Lists?

• No: The problem doesn't involve linked list data structures or operations.

Does the problem have small constraints?

• Yes: The constraint is n pairs of parentheses where n ranges from 1 to 8. This is a small constraint that makes exhaustive search feasible. With n = 8, we'd have at most 16 characters (8 opening and 8 closing parentheses).

Brute force / Backtracking?

• Yes: Given the small constraints and the need to generate all valid combinations, backtracking is the appropriate approach. We systematically explore all possible ways to place parentheses while pruning invalid paths (like having more closing than opening parentheses at any point).

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This aligns perfectly with the solution, which uses DFS with pruning to generate all valid parentheses combinations by:

• Recursively trying to add either ( or )
• Backtracking when invalid conditions are met
• Collecting valid complete combinations when we've used all n pairs

Intuition

The key insight is recognizing that we're building strings character by character, where at each step we have a choice: add ( or add ). This naturally forms a decision tree structure.

Think of it like this: if we need n = 2 pairs, we're placing 2 opening and 2 closing parentheses. We could try all possible arrangements like (()), ()(), ))((, etc., but most would be invalid.

What makes a combination invalid? Two rules emerge:

1. We can't use more than n of each type of parenthesis
2. At any point while building left-to-right, we can't have more ) than ( (because each ) needs a matching ( before it)

This suggests a backtracking approach where we:

• Start with an empty string
• At each step, try adding ( if we haven't used all n opening brackets
• Try adding ) if it won't exceed the number of ( we've placed
• When we've placed exactly n of each type, we have a valid combination

The beauty of this approach is that by checking our constraints as we build (rather than generating everything and filtering later), we avoid exploring paths that can never lead to valid solutions. For example, if we've already placed 3 closing brackets but only 2 opening brackets, we immediately know this path is invalid and backtrack.

This "build incrementally and prune early" strategy is much more efficient than generating all possible strings of length 2n and then checking validity, especially as n grows larger.

Learn more about Dynamic Programming and Backtracking patterns.

Solution Approach

The solution implements a depth-first search (DFS) with pruning to generate all valid parentheses combinations.

Core Algorithm Structure:

The solution uses a recursive helper function dfs(l, r, t) where:

• l: count of left parentheses ( added so far
• r: count of right parentheses ) added so far
• t: the current string being built

Pruning Conditions:

The function first checks three invalid conditions to prune the search tree:

1. l > n: We've used too many left parentheses
2. r > n: We've used too many right parentheses
3. l < r: We have more right parentheses than left (invalid at any point)

If any of these conditions are true, we immediately return without exploring further.

Base Case:

When l == n and r == n, we've successfully placed all n pairs of parentheses. The current string t is a valid combination, so we add it to our answer list.

Recursive Exploration:

If we haven't reached the base case and haven't been pruned, we explore two possibilities:

1. Add a left parenthesis: dfs(l + 1, r, t + '(')
2. Add a right parenthesis: dfs(l, r + 1, t + ')')

Implementation Flow:

1. Initialize an empty answer list ans
2. Start the DFS with dfs(0, 0, '') - no parentheses placed yet
3. The DFS explores all valid paths, building strings character by character
4. Valid complete combinations are collected in ans
5. Return the final list of all valid combinations

The time complexity is O(4^n / √n) which represents the nth Catalan number - the actual count of valid parentheses combinations. The space complexity is O(n) for the recursion stack depth.

Example Walkthrough

Let's trace through the algorithm with n = 2 to see how it generates all valid combinations.

We start with dfs(0, 0, "") - no parentheses placed yet.

Step 1: From dfs(0, 0, "")

• Check conditions: l=0 ≤ 2, r=0 ≤ 2, l=0 ≥ r=0 ✓ All valid
• Not a complete solution yet (need l=2, r=2)
• Try adding (: Call dfs(1, 0, "(")
• Try adding ): Call dfs(0, 1, ")")

Step 2: Exploring dfs(1, 0, "(")

• Conditions valid: l=1 ≤ 2, r=0 ≤ 2, l=1 ≥ r=0 ✓
• Try adding (: Call dfs(2, 0, "((")
• Try adding ): Call dfs(1, 1, "()")

Step 3: Exploring dfs(2, 0, "((")

• Conditions valid: l=2 ≤ 2, r=0 ≤ 2, l=2 ≥ r=0 ✓
• Try adding (: Call dfs(3, 0, "(((")
• Try adding ): Call dfs(2, 1, "(()")

Step 4: dfs(3, 0, "(((")

• Check: l=3 > 2 ✗ Too many left parentheses!
• PRUNE - return immediately

Step 5: Exploring dfs(2, 1, "(()")

• Conditions valid: l=2 ≤ 2, r=1 ≤ 2, l=2 ≥ r=1 ✓
• Try adding (: Call dfs(3, 1, "(()(")
• Try adding ): Call dfs(2, 2, "(())")

Step 6: dfs(3, 1, "(()(")

• Check: l=3 > 2 ✗ Too many left parentheses!
• PRUNE - return immediately

Step 7: dfs(2, 2, "(())")

• Check: l=2 = n and r=2 = n ✓
• Found valid combination! Add "(())" to answer list
• Return

Step 8: Back to Step 2, now exploring dfs(1, 1, "()")

• Conditions valid: l=1 ≤ 2, r=1 ≤ 2, l=1 ≥ r=1 ✓
• Try adding (: Call dfs(2, 1, "()(")
• Try adding ): Call dfs(1, 2, "())")

Step 9: Exploring dfs(2, 1, "()(")

• Conditions valid: l=2 ≤ 2, r=1 ≤ 2, l=2 ≥ r=1 ✓
• Try adding (: Call dfs(3, 1, "()((")
• Try adding ): Call dfs(2, 2, "()()")

Step 10: dfs(3, 1, "()((")

• Check: l=3 > 2 ✗
• PRUNE - return immediately

Step 11: dfs(2, 2, "()()")

• Check: l=2 = n and r=2 = n ✓
• Found valid combination! Add "()()" to answer list
• Return

Step 12: Back to Step 8, exploring dfs(1, 2, "())")

• Check: l=1 < r=2 ✗ More closing than opening!
• PRUNE - return immediately

Step 13: Back to Step 1, exploring dfs(0, 1, ")")

• Check: l=0 < r=1 ✗ Starting with ) means more closing than opening!
• PRUNE - return immediately

Final Result: ["(())", "()()"]

The algorithm efficiently explored only valid paths, pruning branches that would lead to invalid combinations. Out of potentially 2^4 = 16 possible arrangements of 4 parentheses, we only explored the promising paths and found the 2 valid combinations.

Solution Implementation

Time and Space Complexity

The time complexity is O(4^n / √n), which can be loosely bounded by O(4^n). This is because the code explores a binary tree where at each step we can either add a left parenthesis or a right parenthesis, creating a tree with maximum depth 2n. However, due to pruning conditions (l < r and l > n), not all branches are explored. The actual number of valid combinations is the n-th Catalan number, which is approximately 4^n / (n^(3/2) * √π). Each valid path requires O(n) time to construct and append the string, so the total time complexity is O(4^n / √n * n) = O(4^n * √n).

The reference answer O(2^(n×2) × n) = O(2^(2n) × n) = O(4^n × n) is a valid upper bound since 2^(2n) = 4^n, and multiplying by n accounts for string operations.

The space complexity is O(n) for the recursion call stack depth, which can go up to 2n levels deep in the worst case, so it's O(2n) = O(n). Additionally, we need to consider the space for storing the temporary string t during recursion, which also takes O(n) space. The output list is not counted as part of the space complexity as it's the required output. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Pruning Logic Order

Pitfall: A common mistake is checking left_count < right_count before verifying that counts are within bounds. This can lead to exploring invalid paths where right_count > n but left_count is even larger.

Incorrect Implementation:

def backtrack(left_count, right_count, current_string):
    # Wrong: checking balance before bounds
    if left_count < right_count:
        return
    if left_count > n or right_count > n:
        return

Why it's problematic: If left_count = 4, right_count = 5, n = 3, the first condition doesn't catch this invalid state, and we might continue processing before the second check.

Correct Implementation:

def backtrack(left_count, right_count, current_string):
    # Check all invalid conditions together
    if left_count > n or right_count > n or left_count < right_count:
        return

2. String Concatenation Performance Issue

Pitfall: In languages where strings are immutable, repeatedly concatenating strings creates new objects each time, leading to O(n²) overhead per generated string.

Inefficient Approach:

def backtrack(left_count, right_count, current_string):
    # String concatenation creates new string objects
    backtrack(left_count + 1, right_count, current_string + '(')
    backtrack(left_count, right_count + 1, current_string + ')')

Optimized Solution Using List:

def generateParenthesis(self, n: int) -> List[str]:
    def backtrack(left_count, right_count):
        if left_count > n or right_count > n or left_count < right_count:
            return
      
        if left_count == n and right_count == n:
            result.append(''.join(path))
            return
      
        # Use list for O(1) append/pop operations
        path.append('(')
        backtrack(left_count + 1, right_count)
        path.pop()
      
        path.append(')')
        backtrack(left_count, right_count + 1)
        path.pop()
  
    result = []
    path = []
    backtrack(0, 0)
    return result

3. Missing Early Termination Optimization

Pitfall: Not implementing an optimization to stop adding closing parentheses when we've already placed all opening ones.

Suboptimal Logic:

def backtrack(left_count, right_count, current_string):
    # Always tries both branches even when unnecessary
    backtrack(left_count + 1, right_count, current_string + '(')
    backtrack(left_count, right_count + 1, current_string + ')')

Optimized Version:

def backtrack(left_count, right_count, current_string):
    if left_count == n and right_count == n:
        result.append(current_string)
        return
  
    # Only add opening parenthesis if we haven't used all n
    if left_count < n:
        backtrack(left_count + 1, right_count, current_string + '(')
  
    # Only add closing parenthesis if it maintains validity
    if right_count < left_count:
        backtrack(left_count, right_count + 1, current_string + ')')

This optimization reduces unnecessary recursive calls by checking conditions before making the recursive call rather than after.