Generate Parentheses — Backtracking

What does it solve?

Given n, generate all valid strings of n pairs of parentheses. A string is valid when every opening bracket has a matching closing bracket in the right order.

Rather than generating all 2²ⁿ possibilities and filtering, backtracking builds the string character by character — only placing a bracket when it's legal to do so.

The core idea

// two pruning rules:
if open < n: place '(', open++
if close < open: place ')', close++
if open == close == n: // found one!
results.push(current)
// backtrack after each choice

Complexity

Time complexity

O(4ⁿ/√n)

The number of valid combinations (Catalan number Cₙ). The pruning keeps us far below 2²ⁿ brute force.

Space complexity

O(n)

Recursion depth is at most 2n — and the current string being built is at most 2n characters long.

Examples

Custom n

Enter any n from 1–8 to run the algorithm on your own input (larger values produce longer walkthroughs).

Live animation

open bracket added close bracket added backtracking complete solution

Current string being built

Step — of —

Open count

—

Close count

—

Action

—

Solutions found

—

Solutions found so far

none yet

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step iteration

Step	Action	open	close	Current string	Solutions

Implementation

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

char** result;
int resultCount;
int resultCapacity;

void addResult(char* s) {
    if (resultCount >= resultCapacity) {
        resultCapacity *= 2;
        result = realloc(result, sizeof(char*) * resultCapacity);
    }
    result[resultCount] = malloc(strlen(s) + 1);
    strcpy(result[resultCount], s);
    resultCount++;
}

void backtrack(char* current, int open, int close, int n) {
    if (open == n && close == n) {
        addResult(current);
        return;
    }
    int len = strlen(current);
    if (open < n) {
        current[len] = '(';
        current[len + 1] = '\0';
        backtrack(current, open + 1, close, n);
        current[len] = '\0';
    }
    if (close < open) {
        current[len] = ')';
        current[len + 1] = '\0';
        backtrack(current, open, close + 1, n);
        current[len] = '\0';
    }
}

char** generateParenthesis(int n, int* returnSize) {
    resultCapacity = 16;
    resultCount = 0;
    result = malloc(sizeof(char*) * resultCapacity);
    char* current = malloc(2 * n + 1);
    current[0] = '\0';
    backtrack(current, 0, 0, n);
    free(current);
    *returnSize = resultCount;
    return result;
}

int main() {
    int n = 3, size;
    char** res = generateParenthesis(n, &size);
    for (int i = 0; i < size; i++) {
        printf("%s\n", res[i]);
        free(res[i]);
    }
    free(res);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void backtrack(string current, int open, int close, int n,
             vector<string>& results) {
    if (open == n && close == n) {
        results.push_back(current);  // found a complete valid string
        return;
    }
    if (open < n) {           // can still add an opening bracket
        backtrack(current + "(", open + 1, close, n, results);
    }
    if (close < open) {       // can add a closing bracket
        backtrack(current + ")", open, close + 1, n, results);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> results;
    backtrack("", 0, 0, n, results);
    return results;
}

int main() {
    for (auto& s : generateParenthesis(3))
        cout << s << "\n";
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<>();
        backtrack("", 0, 0, n, results);
        return results;
    }

    private void backtrack(String current, int open, int close,
                           int n, List<String> results) {
        if (open == n && close == n) {
            results.add(current);
            return;
        }
        if (open < n) {
            backtrack(current + "(", open + 1, close, n, results);
        }
        if (close < open) {
            backtrack(current + ")", open, close + 1, n, results);
        }
    }

    public static void main(String[] args) {
        GenerateParentheses sol = new GenerateParentheses();
        System.out.println(sol.generateParenthesis(3));
    }
}

function generateParenthesis(n) {
    const results = [];

    function backtrack(current, open, close) {
        if (open === n && close === n) {
            results.push(current);
            return;
        }
        if (open < n) {
            backtrack(current + "(", open + 1, close);
        }
        if (close < open) {
            backtrack(current + ")", open, close + 1);
        }
    }

    backtrack("", 0, 0);
    return results;
}

// Usage
console.log(generateParenthesis(3));
// Output: ["((()))","(()())","(())()","()(())","()()()"]

from typing import List

def generateParenthesis(n: int) -> List[str]:
    results = []

    def backtrack(current: str, open_count: int, close_count: int):
        if open_count == n and close_count == n:
            results.append(current)
            return
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return results

# Usage
print(generateParenthesis(3))
# Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars