Generate Parentheses - Practice Coding Problems

Generate Parentheses - Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

A well-formed parentheses string means:

Every opening parenthesis '(' has a corresponding closing parenthesis ')'
Parentheses are properly nested (no closing before matching opening)
All parentheses are matched

Example: For n = 3, valid combinations include "((()))", "(()())", "(())(), "()(())", "()()()"

Input & Output

Example 1 — Basic Case

$ Input: n = 3

› Output: ["((()))","(()())","(())()","()(())","()()()"]

💡 Note: For n=3, we need 3 opening and 3 closing parentheses. The 5 valid combinations are: ((())), (()()), (())(), ()(())], and ()()().

Example 2 — Minimum Case

$ Input: n = 1

› Output: ["()"]

💡 Note: With only 1 pair of parentheses, there's only one valid combination: ()

Example 3 — Small Case

$ Input: n = 2

› Output: ["(())","()()"]

💡 Note: For n=2, we have 2 valid ways to arrange 2 pairs: nested (()) or sequential ()()

Constraints

1 ≤ n ≤ 8

Visualization

Tap to expand

Understanding the Visualization

Input

Given n pairs of parentheses to arrange

Process

Generate all valid balanced combinations

Output

Return array of valid parentheses strings

Key Takeaway

🎯 Key Insight: Track open/close counts during backtracking to ensure we never violate parentheses balance rules

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to use backtracking to build valid parentheses strings by tracking open and close counts. Best approach is backtracking which only generates valid combinations. Time: O(4^n / √n), Space: O(4^n / √n)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(4^n / √n)	O(4^n / √n)	Cache results of subproblems to avoid redundant computation
Backtracking - Build Valid Strings	O(4^n / √n)	O(4^n / √n)	Build strings character by character, only adding valid characters
Brute Force - Generate All Then Filter	O(2^(2n) * n)	O(2^(2n) * n)	Generate all possible strings with n '(' and n ')', then filter valid ones

Dynamic Programming with Memoization — Algorithm Steps

Define recursive function with parameters for remaining opens and closes
Use memoization to cache results for each state
Combine cached results to build final answer
Return all unique valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

State Space

Each (open_left, close_left) pair is a unique state

Cache Results

Store results to avoid recomputation

Combine

Build final answer from cached subproblems

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Simplified implementation without hash map for C
void backtrack(char result[][20], int* count, char* current, int pos, int openCount, int closeCount, int n) {
    if (pos == 2 * n) {
        strcpy(result[*count], current);
        (*count)++;
        return;
    }
    
    if (openCount < n) {
        current[pos] = '(';
        current[pos + 1] = '\0';
        backtrack(result, count, current, pos + 1, openCount + 1, closeCount, n);
    }
    
    if (closeCount < openCount) {
        current[pos] = ')';
        current[pos + 1] = '\0';
        backtrack(result, count, current, pos + 1, openCount, closeCount + 1, n);
    }
}

int solution(int n, char result[][20]) {
    char current[20] = "";
    int count = 0;
    backtrack(result, &count, current, 0, 0, 0, n);
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char result[1000][20];
    int count = solution(n, result);
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("\"%s\"", result[i]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^n / √n)

Same as backtracking since subproblems don't overlap significantly

✓ Linear Growth

Space Complexity

O(4^n / √n)

Memoization cache plus space for storing all valid combinations

⚡ Linearithmic Space

52.0K Views

High Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler