The O(n) Club: Generate Parentheses — How to Host a Backtracking Party (No Unmatched Guests)

The O(n) Club: Generate Parentheses — How to Host a Backtracking Party (No Unmatched Guests)

⚡ TL;DR

Want every way to juggle n pairs of parentheses without summoning the runtime demons? Backtracking creates valid combos from the start. Brute force? Only if your machine’s powered by regret.

// Java quick-start
List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, "", 0, 0, n);
    return res;
}

🧠 How Devs Usually Mess This Up

Some devs try producing every combo of ‘(‘ and ‘)’ and then bin the failures, as if CPU cycles are infinite and time isn’t real. That’s 2²ⁿ combos! Filtering valid strings after is like baking the whole bakery and tossing out burnt cookies. Others forget that every ‘(‘ is unique, so (()()) and (())() aren’t the same shindig. The worst offense? Letting more ‘)’ than ‘(‘ crash the party. That’s not a feature, it’s a bug buffet.

🔍 What’s Actually Going On

Picture recursion as a picky nightclub bouncer: only let in a ‘(‘ if you haven’t already maxed out your n openers. And you can’t let in a ‘)’ unless there’s already an unmatched ‘(‘. The bouncer won’t allow a closer to leapfrog the opener. Every choice is pre-filtered, like only sending invitations to people who RSVP ‘yes’ in advance. This means we skip all the awkward, broken combos and head right to the afterparty.

🛠️ PseudoCode

• Start: Empty string, 0 openers, 0 closers.
  backtrack(res, current, open, close, n)
• Base Case: If current length == 2*n, it’s golden. Add to results.
• Add ‘(‘ if: open < n.
  backtrack(res, current + "(", open + 1, close, n)
• Add ‘)’ if: close < open.
  backtrack(res, current + ")", open, close + 1, n)

Rinse. Repeat. Never wake up with a mismatched hangover.

💻 The Code

import java.util.*;
 public class ParenthesisGenerator {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;
    }
     private void backtrack(List<String> res, String curr, int open, int close, int n) {
        if (curr.length() == n * 2) {
            res.add(curr);
            return;
        }
        if (open < n) {
            backtrack(res, curr + "(", open + 1, close, n);
        }
        if (close < open) {
            backtrack(res, curr + ")", open, close + 1, n);
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• n = 0? You get one string: "". Don’t overthink it.
• Brute-forcing? Watch stack overflow eat your lunch at n > 10.
• Miss the close < open check, and your results will haunt you — ())( is not a party anyone enjoys.
• Time: O(4ⁿ/sqrt(n)). Space: every valid sequence fits in RAM (unless you try n=25, then you’ll meet swap hell).

🧠 Interviewer Brain-Tattoo

“Letting a ‘)’ in before its buddy ‘(‘ arrives? That’s not backtracking, that’s bugtracting.”