Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Generate Parentheses in Java: Keep Every Prefix Balanced

Build balanced parentheses using remaining counts, understand why close must exceed open, and trace the valid prefix tree.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Generate every balanced string containing n pairs of parentheses. Each output has length 2n. For n=2, both (()) and ()() are valid, but ())( is not: a prefix closes something that has not been opened.

The original task permits 1≤n≤8. Practice on LeetCode. The empty-string result for n=0 is a useful mathematical extension, not a published input example.

Constraints & requirements

CONTRACT
Original task: 1≤n≤8. Track remaining brackets. A close is allowed only when close>open; this means an unmatched opening is available.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    n=3
    Output
    ["((()))","(()())","(())()","()(())","()()()"]

    Five balanced strings; every prefix has at least as many opens as closes.

  2. Example 2 Case 2

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

    Nested and adjacent pairs are both valid.

  3. Example 3 Case 3

    Input
    n=1
    Output
    [()]

    A closing bracket cannot be the first choice.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Never generate a prefix that has more closing than opening brackets.

02Hint 2

With remaining counts, closes may be placed only when close>open.

03Hint 3

When both counts reach zero, store the immutable prefix.

How to think before coding

Write down whether counters mean remaining or already placed brackets. Here they mean REMAINING. An opening is allowed while open>0. A closing is allowed only when close>open, which means an unmatched opening has already been placed. Both counters reaching zero completes one string. This inequality comes from the prefix rule, not from guessing whether the previous character was an opening.

Brute force and the improvement

Generate all 2^(2n)=4^n strings of length 2n, then scan each to reject a negative balance or a nonzero final balance. Checking costs O(n·4^n) time and O(n) working space, excluding valid outputs. The waste starts as soon as a prefix closes an unopened bracket. Instead of generating the rest of that branch, reject it immediately. The improved generator keeps only legal prefixes; a shared builder is a further copy-saving optimization, described in complexity below.

Intuition: prevent invalid prefixes immediately

Checking only the final count is insufficient. )( has one open and one close but is invalid. At every prefix, placed closing brackets must not outnumber placed openings.

Your solution tracks remaining counts. If open and close both start at n, placed opens equal n-open; placed closes equal n-close. There is an unmatched opening exactly when n-open > n-close, which simplifies to close > open.

This strict inequality explains the condition without inspecting the last character. The last character alone cannot decide whether another close is legal: (()) contains two consecutive closes, and both are correct.

Algorithm

  1. Start with n remaining openings, n remaining closings and an empty prefix.
  2. Save the prefix when both counts reach zero.
  3. Add ( if an opening remains.
  4. Add ) only if close>open, meaning one unmatched opening exists.

Try opening first for dictionary order with ( before ). Each concatenation creates a new String, so the parent’s prefix does not need an explicit delete operation.

Java solution

The counters represent remaining brackets. The strict close > open condition ensures that every closing bracket has an unmatched opening.

Java
import java.util.*;

class Solution {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        brackets(n, n, "", result); // Counts mean REMAINING opening and closing parentheses.
        return result;
    }
    private static void brackets(int open, int close, String prefix, List<String> result) {
        if (open == 0 && close == 0) { // Exactly n pairs have been placed.
            result.add(prefix); // Strings are immutable; no snapshot copy is needed.
            return;
        }
        if (open > 0) brackets(open - 1, close, prefix + "(", result); // An opening is safe if available.
        if (close > open) brackets(open, close - 1, prefix + ")", result); // Close only an unmatched opening.
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3)); // Five strings: "((()))", "(()())", "(())()", "()(())", "()()()"
    }
}

For n=3 the five strings are "((()))", "(()())", "(())()", "()(())", and "()()()". Java’s list display omits the quotation marks; they are shown here to make each string’s boundary clear.

Recursion tree and dry run

Numbered illustrated dry run for Generate Parentheses; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: n = 2

What to track: open and close mean counts still available, not counts already used. Each child gets a new immutable prefix string. This is the complete small traversal.

  1. Only an opening is legal initially

    Java operationif (open > 0) brackets(open - 1, close, prefix + "(", result);
    Stateroot (open=2, close=2, prefix="") creates (1,2,"(")

    close > open is false at the root, so a leading closing bracket never gets a child call.

  2. Use the other opening

    Java operationif (open > 0) brackets(open - 1, close, prefix + "(", result);
    State(open=0, close=2, prefix="((")

    No openings remain. There are two unmatched openings to close.

  3. Close twice and save

    Java operationif (close > open) brackets(open, close - 1, prefix + ")", result);
    State(0,1,"(()") → (0,0,"(())"); result = ["(())"]

    Each closing branch is legal because an unmatched opening exists. Both zero counts mark a complete answer.

  4. Resume the one-opening prefix

    Java operationif (close > open) brackets(open, close - 1, prefix + ")", result);
    Statewaiting frame (1,2,"(") creates (1,1,"()")

    The parent’s prefix is still "("; returning children never modified it. No explicit remove operation is needed.

  5. Open, then close the second pair

    Java operationresult.add(prefix);
    State(1,1,"()") → (0,1,"()(") → (0,0,"()()"); result has both strings

    At (1,1), closing is forbidden until the remaining opening is used. The final base case saves the second answer.

Final result: ["(())","()()"]

Worked example · read from top to bottom
"" (open=2, close=2)
└─ "(" (1,2)
   ├─ "((" (0,2)
   │  └─ "(()" (0,1)
   │     └─ "(())" (0,0) → save
   └─ "()" (1,1)
      └─ "()(" (0,1)
         └─ "()()" (0,0) → save

At "()", close equals open, so another ) is blocked. The only legal next action is (. A blocked choice does not create a recursive call and should not appear as an explored tree node.

Why it works

Open is added only while available, so we never exceed n openings. Close is added only to match an existing unmatched opening, so every generated prefix is valid. The leaf uses exactly n of each. Conversely, every well-formed string obeys these same prefix conditions, so its sequence of choices is never blocked and reaches a leaf once.

Complexity and alternative approaches

There are Cₙ balanced outputs, where Cₙ is the nth Catalan number. Writing the returned characters alone costs Ω(n·Cₙ). For this valid-prefix generator, a safe bound including String concatenation is O(n²·Cₙ): there are at most O(n·Cₙ) valid-prefix nodes and creating a new prefix copies up to 2n characters. Auxiliary live string storage can be O(n²) along a deep call chain, plus O(n) frames; output uses O(n·Cₙ).

A shared StringBuilder with append, recurse and delete avoids copying each intermediate prefix and supports O(n·Cₙ) generation/copy work with O(n) auxiliary space. The immutable-string version is intentionally kept close to your code and easy to reason about for the small input bound.

Generating all 2^(2n) bracket strings and checking each one is correct but explores many invalid prefixes. Catalan DP can count balanced strings, but a count is not the requested list.

Common mistakes

  • Using close≥open permits a closing bracket at the beginning.
  • Forgetting whether counters mean placed or remaining reverses the inequality.
  • Disallowing consecutive ) rejects valid nesting.
  • Saving when only one count reaches zero produces incomplete strings.

Practice next

Next lessonbinary strings without consecutive ones

Back to Recursion and backtracking →