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

Problem: Generate Parentheses

Explore how to generate all possible well-formed parentheses strings for a given number of pairs using recursion and backtracking techniques. Learn to implement this in C# by managing the counts of opening and closing parentheses to ensure valid combinations. This lesson helps you develop a clear understanding of recursive problem-solving and algorithm complexity related to generating parentheses.

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 C# in the following coding playground.

C#
usercode > Solution.cs
using System.Collections.Generic;
public class Solution
{
    public List<string> GenerateParenthesis(int n)
    {
        // Replace this placeholder return statement with your code
        return new List<string>();
    }
}
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:

GenerateParenthesis(n): Main method 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 local helper method 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 ...