Every Well-Formed Bracket Sequence of a Given Length

Medium20–25 min

Topics

BacktrackingRecursionString

Companies

AmazonGoogleFacebook

Given a count n, produce every string of length 2n made of n opening and n closing brackets that is well-formed — every prefix has at least as many opens as closes, and the whole string balances out to zero by the end. Trying every character independently at every position and checking validity only once a string is complete works, but wastes enormous effort on prefixes that were already unrecoverable — a string beginning with a closing bracket is built out to full length before that fact is even noticed. Tracking how many opens and closes have been placed so far, and only ever allowing a placement that keeps the running balance non-negative, means every partial string the search ever holds is one that could still become valid — nothing hopeless is ever built in the first place.

Test Case 1:

Input:n = 4

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

Explanation:4 pairs produce 14 well-formed sequences — the 4th Catalan number.

Test Case 2:

Input:n = 1

Output:["()"]

Explanation:One pair has exactly one valid arrangement.

Test Case 3:

Input:n = 0

Output:[""]

Explanation:Zero pairs means the only valid sequence is the empty string.

Constraints

◆0 ≤ n ≤ 8
◆Every returned string has exactly n opening and n closing brackets
◆Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Try Every Character at Every Position, Validate at the End

Brute

Build every possible string of length 2n by trying both '(' and ')' independently at each position — no rule about validity is applied during construction at all. Only once a full-length string exists does a separate scan check whether it's ever balanced correctly. This finds every valid sequence eventually, but it also fully constructs and checks strings that were doomed from their very first character — a string starting with ')' can never become valid, yet every one of its 2^(2n-1) completions still gets built and rejected one at a time.

TimeO(2²ⁿ · n)

SpaceO(2²ⁿ · n)

Java

Try it out

class Solution {
    public String[] wellFormedBracketSequences(int n) {
        List<String> result = new ArrayList<>();
        char[] current = new char[2 * n];
        generateAll(current, 0, result);
        return result.toArray(new String[0]);
    }

    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (isValid(current)) {
                result.add(new String(current));
            }
            return;
        }
        current[pos] = '(';
        generateAll(current, pos + 1, result);
        current[pos] = ')';
        generateAll(current, pos + 1, result);
    }

    private boolean isValid(char[] s) {
        int balance = 0;
        for (char c : s) {
            balance += (c == '(') ? 1 : -1;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
}

Optimal — Only Place a Bracket That Keeps the Prefix Valid

Optimal

Build the string one character at a time, but only ever place a character that can't already doom the result: '(' is allowed as long as fewer than n have been placed so far, and ')' is allowed only when fewer closes than opens have been placed (so the prefix never goes negative). Every branch this ever explores is therefore a valid prefix of some eventual answer — nothing equivalent to "starts with an unmatched )" is ever constructed, let alone fully built out and then discarded.

TimeO(4ⁿ / √n)

SpaceO(n)