Generate Parentheses

This question looks like a string puzzle. But it is really about choices. At each step you decide what character to place next. Make the right choices and you only build valid answers. This is the classic way interviewers test if you understand backtracking.

🎯 The Problem

You get one number n and must build every valid way to arrange that many pairs of parentheses.

• n is the number of pairs, so you have n open ( and n close ).
• Valid means every ( has a matching ).
• Valid also means no ) ever comes before its (.
• Return every valid combination, not just the count.

A quick read of n = 2. That means two ( and two ). The valid strings are (()) and ()(). A string like )( is not valid, because the close bracket comes first. A string like (() is not valid either, because one open bracket never closes.

Input:  n = 2
Output: ["(())", "()()"]

Explanation: both strings have 2 open and 2 close brackets, all matched.

Here is the rule that keeps a string valid as we build it, drawn as a decision.

🐢 Approach 1: Build All, Then Filter (Brute Force)

Make every string of ( and ), then keep the valid ones.

The idea:

• Generate every string of length 2n using ( and ).
• Check each one for matched brackets.
• Keep only the valid strings.

Why it is weak:

• For length 2n there are 2 raised to the power 2n strings.
• Most of them are junk that you build and throw away.
• For n = 5 that is over a thousand strings, and only a few are valid.
• The wasted work makes it far too slow.

Here is the build-all-then-filter code:

def generate_parenthesis(n):
    def valid(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False
        return balance == 0

    result = []
    def build(text):
        if len(text) == 2 * n:
            if valid(text):
                result.append(text)
            return
        build(text + "(")
        build(text + ")")

    build("")
    return result

⚡ Approach 2: Backtracking (Best)

The idea in one line: build the string one character at a time, but only ever add a character that keeps it valid.

The idea:

• Backtracking means make a choice, go deeper, then undo the choice and try another path.
• Track two counts: how many ( used and how many ) used.

How it works:

• You may add ( only while the open count is still less than n.
• You may add ) only while the close count is still less than the open count.
• That second rule stops you from closing a bracket that was never opened.
• When the string reaches length 2n, both counts hit n, so it is complete and valid. Save it.

Why it is fast:

• We never make an invalid move, so we never build a string we throw away.
• It only visits valid paths and a few dead ends.
• The count of valid strings is the nth Catalan number, which grows far slower than 2 to the power 2n.

Here is a small piece of the choice tree for n = 2. Each box shows the string so far.

Steps to Solve

1. Keep the string so far, the open count, and the close count.
2. If the string length equals 2n, save it and stop this path.
3. If the open count is less than n, add (, go deeper, then remove it.
4. If the close count is less than the open count, add ), go deeper, then remove it.
5. Start the whole thing with an empty string and both counts at zero.

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

void backtrack(char *current, int pos, int open, int close, int n) {
    if (pos == 2 * n) {        // string is full and valid
        current[pos] = '\0';
        printf("%s\n", current);
        return;
    }
    if (open < n) {            // we may still add an open bracket
        current[pos] = '(';
        backtrack(current, pos + 1, open + 1, close, n);
    }
    if (close < open) {        // we may close only if an open is waiting
        current[pos] = ')';
        backtrack(current, pos + 1, open, close + 1, n);
    }
}

int main(void) {
    int n = 2;
    char current[100];
    backtrack(current, 0, 0, 0, n);
    return 0;
}

(())
()()

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void backtrack(vector<string>& result, string current, int open, int close, int n) {
    if ((int)current.size() == 2 * n) {  // full and valid string
        result.push_back(current);
        return;
    }
    if (open < n) {                      // may add an open bracket
        backtrack(result, current + "(", open + 1, close, n);
    }
    if (close < open) {                  // may add a close bracket
        backtrack(result, current + ")", open, close + 1, n);
    }
}

int main() {
    int n = 2;
    vector<string> result;
    backtrack(result, "", 0, 0, n);
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << "\"" << result[i] << "\"";
        if (i + 1 < result.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

["(())", "()()"]

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

public class GenerateParentheses {
    static void backtrack(List<String> result, StringBuilder current, int open, int close, int n) {
        if (current.length() == 2 * n) {   // full and valid string
            result.add(current.toString());
            return;
        }
        if (open < n) {                    // may add an open bracket
            current.append('(');
            backtrack(result, current, open + 1, close, n);
            current.deleteCharAt(current.length() - 1);  // undo the choice
        }
        if (close < open) {                // may add a close bracket
            current.append(')');
            backtrack(result, current, open, close + 1, n);
            current.deleteCharAt(current.length() - 1);  // undo the choice
        }
    }

    public static List<String> generate(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(generate(2));
    }
}

[(()), ()()]

def generate_parentheses(n):
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:        # full and valid string
            result.append(current)
            return
        if open_count < n:               # may add an open bracket
            backtrack(current + "(", open_count + 1, close_count)
        if close_count < open_count:     # may add a close bracket
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result


print(generate_parentheses(2))

['(())', '()()']

function generateParentheses(n) {
  const result = [];

  function backtrack(current, openCount, closeCount) {
    if (current.length === 2 * n) {     // full and valid string
      result.push(current);
      return;
    }
    if (openCount < n) {                // may add an open bracket
      backtrack(current + "(", openCount + 1, closeCount);
    }
    if (closeCount < openCount) {       // may add a close bracket
      backtrack(current + ")", openCount, closeCount + 1);
    }
  }

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

console.log(generateParentheses(2));

[ '(())', '()()' ]

Let us read the Python version line by line and see the reason behind each piece.

The line result = [] holds the finished strings. We collect them here. The inner function backtrack does the real work. It takes three things: the string built so far, the open count, and the close count.

The first check is if len(current) == 2 * n. A full valid string has n opens and n closes, so its length is 2n. When we reach that length, the string is done. We add it to result and return to stop this path.

The next check is if open_count < n. This is the rule for adding an open bracket. We may add ( only while we have not used all n opens. We call backtrack(current + "(", open_count + 1, close_count). Notice we pass current + "(", a brand new string. Because strings in Python do not change in place, the old current stays safe for the next branch. So we do not need to manually undo anything. That is why this version has no explicit delete step, unlike the Java one.

The last check is if close_count < open_count. This is the heart of the trick. We may add ) only when there are more opens than closes. That guarantees every close has a waiting open. We call backtrack again with the close count raised. Finally backtrack("", 0, 0) starts everything from an empty string with both counts at zero.

⏱️ Time and Space Complexity

The count of valid strings for n pairs is the nth Catalan number. A Catalan number is a special counting number that grows fast but far slower than the full 2 to the power 2n. So backtracking only touches valid paths and a few dead ends. The brute force builds all 2 to the power 2n strings, which is much more work. Both store the output, so the space is tied to the number of valid strings times their length.

🧩 Key Takeaways

• ✅ Build only valid strings instead of building everything and filtering.
• ✅ Track the open count and the close count as you go.
• ✅ Add ( only while open is less than n. Add ) only while close is less than open.
• ✅ A string is complete when its length reaches 2n.
• ✅ Backtracking explores far fewer strings than brute force, so it is much faster.

🚀 What’s Next?

• Evaluate Reverse Polish Notation
• Daily Temperatures