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

Problem: Generate Parentheses

Explore how to generate well-formed parentheses strings by applying recursion with backtracking. Understand how to build valid combinations step-by-step, using counters to track opening and closing parentheses, and learn the reasoning behind pruning invalid paths. This lesson helps you implement a recursive algorithm that efficiently enumerates all valid parentheses pairs, deepening your understanding of recursive problem solving.

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.

JavaScript
usercode > Solution.js
function generateParenthesis(n) {
    // Replace this placeholder return statement with your code
    return []
}
export {generateParenthesis};
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 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.

backtrack(current, openCount, closeCount): Recursive helper function that constructs valid parenthesis strings.

  1. Base case: ...