Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Problem: Generate Parentheses

Explore how to generate all valid combinations of n pairs of parentheses using recursion with backtracking. Learn to construct strings step-by-step while maintaining balance between opening and closing parentheses. Understand the use of counters to track the placement of parentheses and the pruning of invalid paths. This lesson helps you implement a recursive solution and analyze its time and space complexity.

We'll cover the following...

Statement

Given an integer n representing the number of pairs of parentheses, generate all possible combinations of well-formed (valid) parentheses strings.

A string of parentheses is considered well-formed if every opening parenthesis ( has a corresponding closing parenthesis ) and they are correctly nested.

Return a list containing all such valid combinations.

Constraints:

  • 1≤1 \leq n ≤8\leq 8

Examples

canvasAnimation-image
1 / 2

Try it yourself!

Implement your solution in the following coding playground.

Python
usercode > Solution.py
def generateParenthesis(n):
    # Replace this placeholder return statement with your code
    return []
Generate Parentheses

Solution

The core idea behind this solution is to use recursion with backtracking to incrementally build valid parentheses strings one character at a time, making choices at each step that guarantee the string remains valid. We maintain two counters, openCount and closeCount, which track how many opening and closing parentheses have been placed so far. At each recursive call, we can add an opening parenthesis ( if we have not yet used all n of them, and we can add a closing parenthesis ) only if the number of closing parentheses placed so far is strictly less than the number of opening parentheses. This invariant ensures that at no point does the string have more closing than opening parentheses, which is the fundamental property of well-formed parentheses. Once the string reaches a length of 2×n2 \times n, we know it is a complete and valid combination, so we add it to our result list. Recursion is a natural fit here because the problem has a branching decision structure: at each position, we explore up to 22 choices and need to enumerate all valid paths through that decision tree.Now, let's look at the solution steps below:

  1. generateParenthesis(n): Main function that generates all valid combinations of n pairs of parentheses.

    1. Initializes an empty result list to collect all valid parenthesis combinations.

    2. Defines a nested helper function backtrack() to recursively build valid combinations.

    3. Starts the recursive process by calling backtrack("", 0, 0) with an empty string and zero counts for both opening and closing parentheses.

    4. Returns the result list containing all well-formed parenthesis combinations.

  2. backtrack(current, openCount, closeCount): Recursive helper function that ...