Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Generate Parentheses

MEDIUMProblemSolveExternal Links

Description

Given an integer n, your task is to generate every possible combination of well-formed (balanced) parentheses using exactly n pairs of opening and closing brackets.

A string of parentheses is considered well-formed if:

  • Every opening bracket ( has a corresponding closing bracket ).
  • At no point while reading the string left to right does the count of closing brackets exceed the count of opening brackets.

Return all such valid combinations as a list of strings. The order of the strings in the result does not matter.

Examples

Example 1

Input: n = 3

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

Explanation: With 3 pairs of parentheses, there are exactly 5 valid combinations. Each string has length 6 (3 opening + 3 closing brackets). Notice that strings like ")()()(" or "(()))" are invalid because the closing brackets appear before their matching openers.

Example 2

Input: n = 1

Output: ["()"]

Explanation: With only 1 pair, there is exactly one valid combination: a single opening bracket followed by a single closing bracket.

Example 3

Input: n = 2

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

Explanation: With 2 pairs, we can either nest them inside each other (()) or place them side by side ()(). The string )()( is invalid because it starts with a closing bracket.

Constraints

  • 1 ≤ n ≤ 8

Editorial

Brute Force

Intuition

The simplest way to think about this problem is: what if we just generated every possible string of length 2n using only the characters ( and ), and then kept only the ones that are valid?

Imagine you have 2n empty slots. For each slot, you can place either ( or ). That gives you 2^(2n) total strings. Most of these will be garbage — like ))))(((( or )()()( — but some will be perfectly balanced. We generate all of them, check each one, and collect the valid ones.

This is like trying every combination on a lock: slow, but guaranteed to find every correct answer.

Step-by-Step Explanation

Let's trace through with n = 2 (total string length = 4). We generate all 2^4 = 16 strings and check each:

Step 1: Generate the first candidate: ((((. Check validity — we have 4 opening and 0 closing brackets. Not balanced (need equal counts). Invalid.

Step 2: Next candidate: (((). Check — 3 opening, 1 closing. Counts unequal. Invalid.

Step 3: Next candidate: (()(.
Check — 3 opening, 1 closing. Counts unequal. Invalid.

Step 4: Next candidate: (()). Check — 2 opening, 2 closing. Scan left to right: after ( open=1, after (( open=2, after (() open=2 close=1, after (()) open=2 close=2. At no point does close exceed open. Valid! Add to results.

Step 5: Next candidate: ()((. Check — 2 opening, 2 closing. But scan: ( ok, () ok, ()( ok, ()(( ends with open=3, close=1. Counts unequal at positions. Actually counts: open=3, close=1 — Unequal. Invalid.

Step 6: Next candidate: ()(). Check — 2 opening, 2 closing. Scan: ( ok, () ok, ()( ok, ()() ok. Counts balanced and close never exceeds open. Valid! Add to results.

Step 7: We continue through all 16 candidates. Most are invalid. Only (()) and ()() survive.

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

Brute Force — Generate All Strings and Validate — Watch how we generate every possible combination of parentheses and check each one for validity, keeping only the balanced strings.

Algorithm

  1. Generate all possible strings of length 2n using characters ( and ) (there are 2^(2n) such strings).
  2. For each generated string, validate it:
    a. Check that it contains exactly n opening and n closing brackets.
    b. Scan left to right, maintaining a running balance (increment on (, decrement on )). If balance ever goes negative, the string is invalid.
    c. If balance is 0 at the end and never went negative, the string is valid.
  3. Collect all valid strings into the result list.
  4. Return the result.

Code

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        int totalLen = 2 * n;
        // Generate all 2^(2n) binary strings
        for (int mask = 0; mask < (1 << totalLen); mask++) {
            string s = "";
            for (int i = 0; i < totalLen; i++) {
                if (mask & (1 << i)) s += ')';
                else s += '(';
            }
            if (isValid(s)) result.push_back(s);
        }
        return result;
    }

private:
    bool isValid(const string& s) {
        int balance = 0;
        for (char c : s) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
};
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []
        total_len = 2 * n

        def is_valid(s: str) -> bool:
            balance = 0
            for ch in s:
                if ch == '(':
                    balance += 1
                else:
                    balance -= 1
                if balance < 0:
                    return False
            return balance == 0

        # Generate all 2^(2n) strings
        for mask in range(1 << total_len):
            s = []
            for i in range(total_len):
                if mask & (1 << i):
                    s.append(')')
                else:
                    s.append('(')
            candidate = ''.join(s)
            if is_valid(candidate):
                result.append(candidate)

        return result
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        int totalLen = 2 * n;
        for (int mask = 0; mask < (1 << totalLen); mask++) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < totalLen; i++) {
                if ((mask & (1 << i)) != 0) sb.append(')');
                else sb.append('(');
            }
            String s = sb.toString();
            if (isValid(s)) result.add(s);
        }
        return result;
    }

    private boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
}

Complexity Analysis

Time Complexity: O(2^(2n) × n)

We generate 2^(2n) candidate strings, and for each candidate, we perform a validity check that scans the entire string of length 2n in O(n) time. For n=8, that's 2^16 = 65,536 candidates, each checked in O(8) time — manageable but wasteful.

Space Complexity: O(n)

We use O(n) space for each candidate string being built. The result list itself stores the valid strings, but that's output space. The auxiliary working space is O(n).

Why This Approach Is Not Efficient

The brute force generates all 2^(2n) possible strings and then filters out the invalid ones. The vast majority of these strings are invalid — for example, with n=3, only 5 out of 64 strings are valid (about 7.8%).

The core problem is that we blindly place ( or ) at every position without considering whether the choice can ever lead to a valid string. We waste time building strings that are doomed from the start — like any string beginning with ) or having more closing brackets than opening ones at any prefix.

Key insight: Instead of generating everything and filtering, what if we only generated strings that could be valid? If we track how many opening and closing brackets we've used so far, we can prune invalid choices early, avoiding the construction of billions of dead-end strings. This leads us to a backtracking approach.

Optimal Approach - Backtracking

Intuition

Instead of generating all strings and filtering, we build valid strings character by character, making smart choices at each step. At every position, we ask:

  1. Can I place an opening bracket (? Yes, but only if I haven't used all n opening brackets yet. (If open_count < n, I can add (.)

  2. Can I place a closing bracket )? Yes, but only if there's an unmatched opening bracket waiting for it. (If close_count < open_count, I can add ).) This rule is the key — it guarantees we never create an invalid prefix.

Think of it like building a sentence where every opening quote must eventually be closed. You wouldn't add a closing quote unless there's already an opening quote that hasn't been matched yet.

This approach is called backtracking because we explore one path (say, placing (), go as deep as possible, then backtrack — undo that choice and try the other option (placing )) — exploring the full tree of possibilities without ever creating an invalid sequence.

Because we prune aggressively (never place ) when it would be invalid), the total number of strings we generate is exactly the n-th Catalan number C(n) = (2n)! / ((n+1)! × n!), which is dramatically smaller than 2^(2n).

Step-by-Step Explanation

Let's trace the backtracking process for n = 2. We build strings character by character, tracking open_count and close_count.

Step 1: Start with an empty string. open=0, close=0. We can only add ( (can't start with ) since close would exceed open).

Step 2: Current = "(". open=1, close=0. We can add ( (open < n=2) or ) (close < open=1). Try ( first.

Step 3: Current = "((". open=2, close=0. We've used all opening brackets (open == n). Can only add ).

Step 4: Current = "(()". open=2, close=1. Can't add ( (open==n). Can add ) (close < open). Add ).

Step 5: Current = "(())". open=2, close=2. Length = 2n = 4. This is a complete valid string! Add "(())" to results.

Step 6: Backtrack to Step 2 where current = "(". Now try the other choice: add ) instead of (.

Step 7: Current = "()". open=1, close=1. Can add ( (open < n=2). Can't add ) (close == open). Add (.

Step 8: Current = "()(". open=2, close=1. Can't add ( (open==n). Can add ) (close < open). Add ).

Step 9: Current = "()()". open=2, close=2. Length = 4. Complete! Add "()()" to results.

Step 10: No more choices to explore. Result = ["(())", "()()"].

Backtracking — Building Valid Parentheses One Character at a Time — Watch the recursion tree grow as we make choices at each position. Opening brackets branch left, closing brackets branch right. Invalid choices are pruned immediately.

Algorithm

  1. Start with an empty string and counters: open_count = 0, close_count = 0.
  2. At each step, make one of two choices:
    • Add ( if open_count < n (we haven't used all n openers)
    • Add ) if close_count < open_count (there's an unmatched opener to close)
  3. When the string reaches length 2n (open_count == n AND close_count == n), add it to the result.
  4. After exploring one choice, backtrack — remove the last character and try the other choice.
  5. Return all collected valid strings.

Code

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }

private:
    void backtrack(vector<string>& result, string& current,
                   int openCount, int closeCount, int n) {
        // Base case: string is complete
        if (current.size() == 2 * n) {
            result.push_back(current);
            return;
        }

        // Choice 1: add '(' if we haven't used all n openers
        if (openCount < n) {
            current.push_back('(');
            backtrack(result, current, openCount + 1, closeCount, n);
            current.pop_back(); // backtrack
        }

        // Choice 2: add ')' if there's an unmatched opener
        if (closeCount < openCount) {
            current.push_back(')');
            backtrack(result, current, openCount, closeCount + 1, n);
            current.pop_back(); // backtrack
        }
    }
};
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []

        def backtrack(current: list[str], open_count: int, close_count: int):
            # Base case: string is complete
            if len(current) == 2 * n:
                result.append(''.join(current))
                return

            # Choice 1: add '(' if we haven't used all n openers
            if open_count < n:
                current.append('(')
                backtrack(current, open_count + 1, close_count)
                current.pop()  # backtrack

            # Choice 2: add ')' if there's an unmatched opener
            if close_count < open_count:
                current.append(')')
                backtrack(current, open_count, close_count + 1)
                current.pop()  # backtrack

        backtrack([], 0, 0)
        return result
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder current,
                           int openCount, int closeCount, int n) {
        // Base case: string is complete
        if (current.length() == 2 * n) {
            result.add(current.toString());
            return;
        }

        // Choice 1: add '(' if we haven't used all n openers
        if (openCount < n) {
            current.append('(');
            backtrack(result, current, openCount + 1, closeCount, n);
            current.deleteCharAt(current.length() - 1); // backtrack
        }

        // Choice 2: add ')' if there's an unmatched opener
        if (closeCount < openCount) {
            current.append(')');
            backtrack(result, current, openCount, closeCount + 1, n);
            current.deleteCharAt(current.length() - 1); // backtrack
        }
    }
}

Complexity Analysis

Time Complexity: O(C(n) × n)

where C(n) is the n-th Catalan number: C(n) = (2n)! / ((n+1)! × n!). This is the number of valid parenthesizations. For each valid string, we spend O(n) time constructing it (appending characters). The Catalan number grows as approximately 4^n / (n^(3/2) × √π), which is exponentially smaller than 2^(2n) = 4^n. For n=8, C(8) = 1430 — we generate exactly 1430 strings instead of brute force's 65,536.

Space Complexity: O(n)

The recursion depth is at most 2n (the length of the string being built). The current string being constructed uses O(n) space. The result list stores C(n) strings of length 2n, but that's output space, not auxiliary space.