Generate combinations of parentheses

Q: What is the difference between generating parentheses with backtracking vs. brute force?

Brute force generates all 2^(2n) strings of length 2n using ( and ), then filters for validity. Backtracking avoids generating invalid strings entirely by only placing a closing parenthesis when there are more open parens than close parens in the current prefix. This pruning dramatically reduces the number of strings explored.

Q: What is the time complexity of generating all valid parentheses combinations?

The number of valid combinations for n pairs is the nth Catalan number, C(n) = (2n)! / ((n+1)! * n!). Each valid string has length 2n, so the output size is O(C(n) * n). The algorithm's time complexity is O(4^n / sqrt(n)) which grows much slower than the brute-force O(2^(2n)) approach because invalid branches are pruned early.

Q: Why do we use a set instead of a list to store the results?

The Firecode version of this problem uses a Set to store results, which guarantees uniqueness. In practice, the backtracking approach with open/close counters never produces duplicates because each recursive path through the tree generates a distinct string. A list would also work correctly here, but the set matches the problem's return type specification.

Q: How do you adapt this solution if the problem asks for a list instead of a set?

Replace the HashSet with an ArrayList (Java), list (Python), or array (JavaScript). The rest of the algorithm stays the same. Since the backtracking approach never generates duplicates, switching from set to list does not affect correctness. Many variations of this problem on different platforms use a list return type.

Q: What are the valid parentheses combinations for n=3?

For n=3, there are exactly 5 valid combinations: ((())), (()()), (())(), ()(()), and ()()(). These correspond to the 3rd Catalan number C(3) = 5. Each string has length 6 (2 * 3) and contains exactly 3 opening and 3 closing parentheses.

Q: How does this problem relate to other backtracking problems?

Generate parentheses is a textbook backtracking problem that shares its core pattern with permutations, combinations, subsets, N-Queens, and Sudoku solvers. The shared pattern is: make a choice, recurse, undo the choice (backtrack). Here, the choices are 'add (' or 'add )' and the constraints determine which choices are valid at each step.

Q: What is the best approach for solving this problem in a coding interview?

Start by writing out the examples for n=1 and n=2 to establish the pattern. Explain that you will use backtracking with two counters tracking remaining open and close parens. Write the recursive helper function with its two branching conditions. Trace through n=2 to verify correctness. Mention that the output count follows Catalan numbers and discuss the time complexity.

You're in a Google phone screen and the interviewer asks you to generate all valid combinations of parentheses for a given number of pairs. It sounds simple at first, but as you start thinking about it, the combinatorial explosion hits. For n=3, there are 5 valid strings. For n=6, there are 132. The brute-force approach of generating every possible string and filtering for validity falls apart quickly. This problem, asked frequently at Amazon, Google, and Facebook, tests whether you can use recursion and backtracking to build only valid strings from the start, pruning the search space as you go.

TL;DR

Use a recursive helper function with two counters: openRemaining and closeRemaining, both starting at n. At each step, add ( if openRemaining > 0, and add ) if closeRemaining > openRemaining (meaning there are unmatched open parens to close). When both counters hit zero, the current string is valid and gets added to the result set. This generates only valid combinations without wasted work, running in time proportional to the Catalan number C(n).

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

Generate parentheses is one of the cleanest introductions to backtracking you will find. Unlike many backtracking problems that require complex state management, this one distills the core technique down to two counters and two branching decisions. It also connects to Catalan numbers, a topic that interviewers love to discuss as a follow-up. Once you understand how the pruning works here, problems like permutations, combinations, and N-Queens become much more approachable.

Understanding the Problem

Given n pairs of parentheses, generate all valid (well-formed) combinations.

Input: An integer n (1 ≤ n ≤ 6) Output: A set of strings where each string contains exactly n opening and n closing parentheses, and every prefix has at least as many ( as ).

For example:

generateParentheses(1) -> ["()"]
generateParentheses(2) -> ["(())", "()()"]
generateParentheses(3) -> ["((()))", "(()())", "(())()", "()(())", "()()()"]

Since the output is a set, ordering does not matter.

What Makes a Combination Valid?

A parentheses string is valid when:

It has exactly n opening and n closing parentheses
At no point while reading left to right does the count of ) exceed the count of (

The string )()( fails rule 2 because the very first character is a closing paren with no matching open. The string (()) passes both rules.

Edge Cases

n = 1: Only one valid combination: ()
n = 2: Two combinations: (()) and ()()
Large n: The count of valid combinations grows following Catalan numbers - 1, 1, 2, 5, 14, 42, 132 for n = 0 through 6

Solution Approach

Think about building a valid parentheses string one character at a time. At each position, you have at most two choices: place ( or place ). But not every choice is valid at every position.

The two rules that govern your choices:

You can add ( whenever you still have opening parens left (openRemaining > 0)
You can add ) only when there are unmatched opens (closeRemaining > openRemaining)

That second condition is the key insight. If closeRemaining equals openRemaining, it means every ( placed so far already has a matching ). Adding another ) would create an invalid prefix.

Loading visualization...

This pruning is what separates backtracking from brute force. Instead of generating all 2^{2n} possible strings and filtering, we only explore paths that can lead to valid results.

The Recursion Tree for n=2

Here is the complete recursion tree for n=2. Each node shows the current string and the remaining counts (openRemaining, closeRemaining):

Loading visualization...

Notice that the tree only has valid paths. There is no node where we placed ) before (, because the pruning condition prevents it. Both leaf nodes produce valid results: (()) and ()().

Tracing the Algorithm

Following the depth-first traversal, here is the first branch that produces (()):

Loading visualization...

After finding (()), the algorithm backtracks to the state where current = "(" and explores the close-paren branch:

Loading visualization...

This produces ()(), completing the exploration for n=2.

Implementation

Here is the solution in Java. The public method initializes the result set and kicks off recursion. The private build method does the actual work.

import java.util.HashSet;
import java.util.Set;

public class Solution {
  public Set<String> generateParentheses(int n) {
    Set<String> result = new HashSet<>();
    build(result, "", n, n);
    return result;
  }

  private void build(
    Set<String> result,
    String current,
    int openRemaining,
    int closeRemaining
  ) {
    // Base case: all parens placed, current string is valid
    if (openRemaining == 0 && closeRemaining == 0) {
      result.add(current);
      return;
    }

    // Choice 1: add an opening parenthesis if any remain
    if (openRemaining > 0) {
      build(result, current + "(", openRemaining - 1, closeRemaining);
    }

    // Choice 2: add a closing parenthesis if there are unmatched opens
    if (closeRemaining > openRemaining) {
      build(result, current + ")", openRemaining, closeRemaining - 1);
    }
  }
}

The build method has three distinct sections:

Base case: When both counters reach zero, the string has exactly n opens and n closes in a valid arrangement. Add it to the result.
Open branch: If openRemaining > 0, we can still place an opening paren. Recurse with current + "(" and decrement openRemaining.
Close branch: If closeRemaining > openRemaining, there are unmatched opening parens in the current string. We can safely add ) to match one of them.

Both branches can execute in the same call, which is what creates the tree structure. When openRemaining is positive and closeRemaining is greater than openRemaining, the function makes two recursive calls, exploring both possibilities.

Why closeRemaining > openRemaining Works

At the start, both counters equal n. When we place (, we decrement openRemaining. When we place ), we decrement closeRemaining.

The difference closeRemaining - openRemaining tells us how many ( characters in the current string don't yet have a matching ). If this difference is zero, every open paren has been closed, and adding another ) would be invalid. If it's positive, there are unclosed opens waiting for their match.

Scaling Up to n=3

For n=3, the recursion tree is larger but follows the same logic. Here are the first few levels:

Loading visualization...

The tree branches more at each level, but the pruning keeps it manageable. The complete exploration produces all five valid combinations:

Loading visualization...

These five combinations are exactly the 3rd Catalan number, C(3) = 5.

Complexity Analysis

Time Complexity

The number of valid parentheses strings for n pairs is the nth Catalan number:

C(n) = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!}

Each valid string has length 2n. The algorithm also explores some partial paths that get pruned, but the total work is bounded by O\left(\frac{4^n}{\sqrt{n}}\right), which is the asymptotic growth rate of the Catalan number times the string length.

For practical values: n=3 produces 5 strings, n=4 produces 14, n=5 produces 42, and n=6 produces 132.

Space Complexity

The recursion stack goes at most 2n levels deep (the length of each complete string). The result set stores C(n) strings, each of length 2n. So the total space is dominated by the output: O(C(n) \cdot n).

If you only count auxiliary space (excluding the output), the recursion stack uses O(n) space.

Common Pitfalls

Using closeRemaining >= openRemaining instead of >: The >= condition would allow adding ) when all opens are matched, producing invalid strings like starting with ).
Forgetting the base case return: Without return after adding to the result set, the method would try to add more parens to a complete string, though in this case the conditions prevent further calls.
Using openRemaining == 0 alone as the base case: You need both counters at zero. If only openRemaining is zero, there may still be closing parens to place.
String concatenation in a loop: For very large n, building strings with + creates many intermediate string objects. Using a StringBuilder (Java) or list of characters (Python) and backtracking in-place is more efficient, though for the constraint n <= 6 it makes no practical difference.

Interview Tips

When presenting this solution:

Start with small examples: Write out the results for n=1 and n=2 by hand. This helps you discover the two branching conditions naturally.
Draw the recursion tree: Sketch the tree for n=2 on the whiteboard. It's small enough to draw completely and clearly shows how pruning works.
State the invariant: "At every step, the current string is a valid prefix - no closing paren appears without a matching open."
Mention Catalan numbers: Knowing that the output size follows Catalan numbers shows mathematical depth. C(n) grows as \frac{4^n}{n^{3/2}\sqrt{\pi}}, which is significantly less than 2^{2n}.
Discuss follow-ups: Interviewers might ask about generating parentheses with multiple bracket types ()[]{}, or about checking validity of a given string (a simpler problem that uses a stack).

Key Takeaways

The two-counter backtracking approach (openRemaining, closeRemaining) generates only valid parentheses strings, avoiding the exponential waste of brute-force generate-and-filter.
The pruning condition closeRemaining > openRemaining is the core of the algorithm. It ensures that at every prefix, opening parens outnumber or equal closing parens.
The output size follows Catalan numbers: 1, 1, 2, 5, 14, 42, 132 for n = 0 through 6. Mentioning this in an interview demonstrates both algorithmic and mathematical understanding.
This problem is a clean template for backtracking. The same pattern of "make a constrained choice, recurse, backtrack" appears in permutations, combinations, N-Queens, and Sudoku.
For n <= 6 (the constraint here), the algorithm runs nearly instantly. The approach scales well because it never explores invalid branches.

Practice and Related Problems

Once you are comfortable with this problem, try these related challenges that build on the same backtracking foundation:

Valid Parentheses - Check if a given string of brackets is valid using a stack
Letter Combinations of a Phone Number - Backtracking with a different set of choices per position
Permutations - Generate all orderings of distinct elements
Combination Sum - Find combinations that sum to a target with backtracking and pruning

Consistent practice is the key to interview success. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Whether you are brushing up on recursion fundamentals or grinding through advanced backtracking problems, building that muscle memory will pay off when it counts.

Solutions in Other Languages

Python

class Solution:
    def generate_parentheses(self, n):
        result = set()
        self.build(result, "", n, n)
        return result

    def build(self, result, current, open_remaining, close_remaining):
        if open_remaining == 0 and close_remaining == 0:
            result.add(current)
            return

        if open_remaining > 0:
            self.build(result, current + "(", open_remaining - 1, close_remaining)

        if close_remaining > open_remaining:
            self.build(result, current + ")", open_remaining, close_remaining - 1)

JavaScript

class Solution {
  generateParentheses(n) {
    const result = new Set();
    this.build(result, "", n, n);
    return result;
  }

  build(result, current, openRemaining, closeRemaining) {
    if (openRemaining === 0 && closeRemaining === 0) {
      result.add(current);
      return;
    }

    if (openRemaining > 0) {
      this.build(result, current + "(", openRemaining - 1, closeRemaining);
    }

    if (closeRemaining > openRemaining) {
      this.build(result, current + ")", openRemaining, closeRemaining - 1);
    }
  }
}

TypeScript

class Solution {
  generateParentheses(n: number): Set<string> {
    const result = new Set<string>();
    this.build(result, "", n, n);
    return result;
  }

  private build(
    result: Set<string>,
    current: string,
    openRemaining: number,
    closeRemaining: number
  ): void {
    if (openRemaining === 0 && closeRemaining === 0) {
      result.add(current);
      return;
    }

    if (openRemaining > 0) {
      this.build(result, current + "(", openRemaining - 1, closeRemaining);
    }

    if (closeRemaining > openRemaining) {
      this.build(result, current + ")", openRemaining, closeRemaining - 1);
    }
  }
}

C++

#include <unordered_set>
#include <string>

class Solution {
public:
  std::unordered_set<std::string> generateParentheses(int n) {
    std::unordered_set<std::string> result;
    build(result, "", n, n);
    return result;
  }

private:
  void build(
      std::unordered_set<std::string> &result,
      std::string current,
      int openRemaining,
      int closeRemaining
  ) {
    if (openRemaining == 0 && closeRemaining == 0) {
      result.insert(current);
      return;
    }

    if (openRemaining > 0) {
      build(result, current + "(", openRemaining - 1, closeRemaining);
    }

    if (closeRemaining > openRemaining) {
      build(result, current + ")", openRemaining, closeRemaining - 1);
    }
  }
};

Go

func GenerateParentheses(n int) map[string]bool {
    result := make(map[string]bool)
    build(result, "", n, n)
    return result
}

func build(result map[string]bool, current string, openRemaining, closeRemaining int) {
    if openRemaining == 0 && closeRemaining == 0 {
        result[current] = true
        return
    }

    if openRemaining > 0 {
        build(result, current+"(", openRemaining-1, closeRemaining)
    }

    if closeRemaining > openRemaining {
        build(result, current+")", openRemaining, closeRemaining-1)
    }
}

Scala

import scala.collection.mutable

class Solution {
  def generateParentheses(n: Int): Set[String] = {
    val result = mutable.Set[String]()
    build(result, "", n, n)
    result.toSet
  }

  private def build(
    result: mutable.Set[String],
    current: String,
    openRemaining: Int,
    closeRemaining: Int
  ): Unit = {
    if (openRemaining == 0 && closeRemaining == 0) {
      result.add(current)
      return
    }

    if (openRemaining > 0) {
      build(result, current + "(", openRemaining - 1, closeRemaining)
    }

    if (closeRemaining > openRemaining) {
      build(result, current + ")", openRemaining, closeRemaining - 1)
    }
  }
}

Kotlin

class Solution {
    fun generateParentheses(n: Int): Set<String> {
        val result = mutableSetOf<String>()
        build(result, "", n, n)
        return result
    }

    private fun build(
        result: MutableSet<String>,
        current: String,
        openRemaining: Int,
        closeRemaining: Int
    ) {
        if (openRemaining == 0 && closeRemaining == 0) {
            result.add(current)
            return
        }

        if (openRemaining > 0) {
            build(result, current + "(", openRemaining - 1, closeRemaining)
        }

        if (closeRemaining > openRemaining) {
            build(result, current + ")", openRemaining, closeRemaining - 1)
        }
    }
}

Swift

class Solution {
    func generateParentheses(_ n: Int) -> Set<String> {
        var result = Set<String>()
        build(&result, "", n, n)
        return result
    }

    private func build(
        _ result: inout Set<String>,
        _ current: String,
        _ openRemaining: Int,
        _ closeRemaining: Int
    ) {
        if openRemaining == 0 && closeRemaining == 0 {
            result.insert(current)
            return
        }

        if openRemaining > 0 {
            build(&result, current + "(", openRemaining - 1, closeRemaining)
        }

        if closeRemaining > openRemaining {
            build(&result, current + ")", openRemaining, closeRemaining - 1)
        }
    }
}

Ruby

require 'set'

class Solution
  def generate_parentheses(n)
    result = Set.new
    build(result, "", n, n)
    result
  end

  def build(result, current, open_remaining, close_remaining)
    if open_remaining == 0 && close_remaining == 0
      result.add(current)
      return
    end

    if open_remaining > 0
      build(result, current + "(", open_remaining - 1, close_remaining)
    end

    if close_remaining > open_remaining
      build(result, current + ")", open_remaining, close_remaining - 1)
    end
  end
end

Rust

use std::collections::HashSet;

impl Solution {
    pub fn generate_parentheses(&self, n: i32) -> HashSet<String> {
        let mut result: HashSet<String> = HashSet::new();
        Self::build(&mut result, String::new(), n, n);
        result
    }

    fn build(
        result: &mut HashSet<String>,
        current: String,
        open_remaining: i32,
        close_remaining: i32,
    ) {
        if open_remaining == 0 && close_remaining == 0 {
            result.insert(current);
            return;
        }

        if open_remaining > 0 {
            Self::build(result, current.clone() + "(", open_remaining - 1, close_remaining);
        }

        if close_remaining > open_remaining {
            Self::build(result, current + ")", open_remaining, close_remaining - 1);
        }
    }
}

C#

public class Solution {
    public HashSet<string> generateParentheses(int n) {
        var result = new HashSet<string>();
        Build(result, "", n, n);
        return result;
    }

    private void Build(
        HashSet<string> result,
        string current,
        int openRemaining,
        int closeRemaining
    ) {
        if (openRemaining == 0 && closeRemaining == 0) {
            result.Add(current);
            return;
        }

        if (openRemaining > 0) {
            Build(result, current + "(", openRemaining - 1, closeRemaining);
        }

        if (closeRemaining > openRemaining) {
            Build(result, current + ")", openRemaining, closeRemaining - 1);
        }
    }
}

Dart

class Solution {
  Set<String> generateParentheses(int n) {
    Set<String> result = {};
    _build(result, "", n, n);
    return result;
  }

  void _build(
    Set<String> result,
    String current,
    int openRemaining,
    int closeRemaining,
  ) {
    if (openRemaining == 0 && closeRemaining == 0) {
      result.add(current);
      return;
    }

    if (openRemaining > 0) {
      _build(result, current + "(", openRemaining - 1, closeRemaining);
    }

    if (closeRemaining > openRemaining) {
      _build(result, current + ")", openRemaining, closeRemaining - 1);
    }
  }
}

PHP

class Solution {
    public function generateParentheses(int $n): array {
        $result = [];
        $this->build($result, "", $n, $n);
        return $result;
    }

    private function build(
        array &$result,
        string $current,
        int $openRemaining,
        int $closeRemaining
    ): void {
        if ($openRemaining === 0 && $closeRemaining === 0) {
            $result[] = $current;
            return;
        }

        if ($openRemaining > 0) {
            $this->build($result, $current . "(", $openRemaining - 1, $closeRemaining);
        }

        if ($closeRemaining > $openRemaining) {
            $this->build($result, $current . ")", $openRemaining, $closeRemaining - 1);
        }
    }
}

Frequently Asked Questions

What is the difference between generating parentheses with backtracking vs. brute force?

Brute force generates all 2^(2n) strings of length 2n using ( and ), then filters for validity. Backtracking avoids generating invalid strings entirely by only placing a closing parenthesis when there are more open parens than close parens in the current prefix. This pruning dramatically reduces the number of strings explored.

What is the time complexity of generating all valid parentheses combinations?

The number of valid combinations for n pairs is the nth Catalan number, C(n) = (2n)! / ((n+1)! * n!). Each valid string has length 2n, so the output size is O(C(n) * n). The algorithm's time complexity is O(4^n / sqrt(n)) which grows much slower than the brute-force O(2^(2n)) approach because invalid branches are pruned early.

Why do we use a set instead of a list to store the results?

The Firecode version of this problem uses a Set to store results, which guarantees uniqueness. In practice, the backtracking approach with open/close counters never produces duplicates because each recursive path through the tree generates a distinct string. A list would also work correctly here, but the set matches the problem's return type specification.

How does the closeRemaining > openRemaining condition ensure validity?

At any point during construction, openRemaining tracks how many ( characters we can still place, and closeRemaining tracks how many ) we can still place. The condition closeRemaining > openRemaining means there are unmatched opening parens in the current string that need closing. If closeRemaining equals openRemaining, every open paren has been closed, so adding ) would create an invalid prefix like ')('

What is the connection between generate parentheses and Catalan numbers?

The number of valid parentheses combinations for n pairs equals the nth Catalan number: C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14. Catalan numbers also count the number of full binary trees with n+1 leaves, the number of ways to triangulate a polygon with n+2 sides, and many other combinatorial structures. This connection is worth mentioning in interviews.

Can this problem be solved iteratively instead of recursively?

Yes, using an explicit stack or queue (BFS approach). Push tuples of (current_string, open_count, close_count) and process them iteratively. The logic is identical: if open_count < n, push with an added (. If close_count < open_count, push with an added ). The recursive approach is cleaner and more natural for interviews, but the iterative version avoids stack overflow for very large n.

How do you adapt this solution if the problem asks for a list instead of a set?

Replace the HashSet with an ArrayList (Java), list (Python), or array (JavaScript). The rest of the algorithm stays the same. Since the backtracking approach never generates duplicates, switching from set to list does not affect correctness. Many variations of this problem on different platforms use a list return type.

What are the valid parentheses combinations for n=3?

For n=3, there are exactly 5 valid combinations: ((())), (()()), (())(), ()(()), and ()()(). These correspond to the 3rd Catalan number C(3) = 5. Each string has length 6 (2 * 3) and contains exactly 3 opening and 3 closing parentheses.

How does this problem relate to other backtracking problems?

Generate parentheses is a textbook backtracking problem that shares its core pattern with permutations, combinations, subsets, N-Queens, and Sudoku solvers. The shared pattern is: make a choice, recurse, undo the choice (backtrack). Here, the choices are 'add (' or 'add )' and the constraints determine which choices are valid at each step.

What is the best approach for solving this problem in a coding interview?

Start by writing out the examples for n=1 and n=2 to establish the pattern. Explain that you will use backtracking with two counters tracking remaining open and close parens. Write the recursive helper function with its two branching conditions. Trace through n=2 to verify correctness. Mention that the output count follows Catalan numbers and discuss the time complexity.