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

Problem: Generate Parentheses

Explore the generation of all valid parentheses strings using recursion and backtracking. Learn to implement a solution that incrementally builds valid sequences by controlling opening and closing parentheses placements. Understand the algorithm's branching logic, constraints for well-formed strings, and analyze its time and space complexity based on Catalan numbers.

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.

Java
usercode > Solution.java
import java.util.*;
class Solution {
    public List<String> generateParenthesis(int n) {
        // Replace this placeholder return statement with your code
        return new ArrayList<>();
    }
}
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(int n): Main method that generates all valid combinations of n pairs of parentheses.

    1. Initializes an empty List<String> called result to collect all valid parenthesis combinations.

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

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

  2. backtrack(String current, int openCount, int closeCount, int n, List<String> result): Recursive helper method that constructs valid parenthesis strings.

    1. Base case: If the length of current equals 2 * n, a ...