02.GenerateParanthesis.md

Generate Parentheses 🧩🔁

Problem statement 📝

Given n pairs of parentheses, return all possible strings of length 2n that are well-formed (balanced).

Examples:

• n = 1 → ["()"]
• n = 2 → ["(())", "()()"] (order may vary)
• n = 3 → ["((()))","(()())","(())()","()(())","()()()"]

Intuition ✨

• A valid parentheses string must never have more ) than ( at any prefix.

• At any step we can:

  • Add '(' if we still have remaining opens (open < n).
  • Add ')' only if there are unmatched opens (close < open).

• Using these rules, we never create invalid partial strings, so we prune invalid branches early — essential for efficiency.

This is a classic backtracking problem: build the string char-by-char, branching only when rules allow it, and backtrack after returning from recursion.

Brute-force approach (not recommended) 🐢

Generate all 2n-length strings of '(' and ')' (2^(2n) possibilities), then check each for validity (balanced & prefix condition). This is exponentially wasteful and infeasible beyond small n.

Optimal approach - Backtracking (DFS) ✅

Backtracking constructs only valid prefixes. For each prefix we track:

• open: how many '(' used so far.
• close: how many ')' used so far.

Transitions:

• If open < n, append '(' and recurse with open+1.
• If close < open, append ')' and recurse with close+1.
• Stop and record when curr.length() == 2*n.

This visits exactly the space of valid parentheses strings — i.e. Cₙ leaves — and does O(n) work per result (building strings), so runtime is O(Cₙ * n).

Complexity analysis 📊

Let Cₙ be the nth Catalan number (Cₙ = (1/(n+1)) * (2n choose n)).

• Number of outputs: Cₙ (approx ≈ 4^n / (n^{3/2} * sqrt(pi))).
• Time complexity: O(Cₙ * n). Each valid string has length 2n (cost to build/copy) and we do constant work per recursion step.
• Space complexity: O(n) recursion depth + O(n) for one working string buffer. Output storage costs O(Cₙ * n).

Note: any algorithm that lists all valid parentheses must take at least O(Cₙ * n) time because output itself has that size.

Implementation code

    vector<string> generateParenthesis(int n) {
        vector<string> res;

        parenthesis("", 0, 0, n, res);
        return res;
    }

    void parenthesis(string curr, int open, int close, int n, vector<string>& res) {
        if (curr.length() == 2 * n) {
            res.push_back(curr);
            return;
        }

        if (open < n)
            parenthesis(curr + '(', open+1, close, n, res);
        if (close < open)
            parenthesis(curr + ')', open, close+1, n, res);
    }

Variants: You can also implement backtrack with an index and a pre-sized string curr(2*n, ' ') and assign curr[pos] = '(' / curr[pos] = ')' to avoid push_back/pop_back. Both are fine; push_back with reserve is simple and efficient.

Example walkthrough (n = 3)

Start with "" (open=0, close=0):

1. Add '(' → "(" (1,0)
2. Add '(' → "((" (2,0)
3. Add '(' → "(((" (3,0)
4. Add ')' → "((()" (3,1)
5. Add ')' → "((())" (3,2)
6. Add ')' → "((()))" (3,3) → record Backtrack and explore other branches such as "(()())", "(())()", "()(())", "()()()".

---

Test cases 🧪

n	Expected outputs (order may vary)
0	[] or [""] depending on convention; our implementation returns [] (we require n>0)
1	["()"]
2	["(())","()()"]
3	["((()))","(()())","(())()","()(())","()()()"]
4	14 strings (Catalan(4) = 14)
Large n (e.g., 8)	Generates C₈ = 1430 strings — verify performance & memory

Edge cases:

• n = 0 → If the problem expects [""] you can handle it explicitly; many LeetCode versions expect [""]. To return [""], change if (n <= 0) return {""};.
• Very large n (≥ 14) will produce many outputs (Catalan grows fast) — be mindful of memory/time.

Tips & tricks ✨

• Reserve capacity in string to avoid repeated reallocations: curr.reserve(2*n).
• Use in-place backtracking (push/pop) to avoid string copies.
• Prune early: the two conditions (open < n, close < open) are natural prunes — they dramatically reduce the search space vs brute-force.
• Iterative solutions exist (using stack + state) but are usually more verbose and not faster.
• If you only need to count valid sequences, use Catalan numbers (no backtracking needed).
• Order of results: DFS order yields lexicographic-ish order if you always try '(' before ')'.

Variations & related problems 🔁

• Generate well-formed strings for different parentheses types (e.g., [], {}) — extend state or treat as multiple brackets with stack validation.
• Generate k-th valid parentheses — use DP counting to skip branches (advanced).
• Count valid parentheses — return Cₙ (Catalan number). Compute via DP or combinatorics.
• All permutations of parentheses with constraints — generalize rules accordingly.