# 015 — Generate Parentheses

<div class="problem-source" markdown="1">

<p class="source-label" id="source">Problem link ও উৎস</p>

- **Original source:** Classic backtracking exercise (valid parenthesis strings)
- **Platform:** LeetCode — <https://leetcode.com/problems/generate-parentheses/>
- **Topic:** recursion / backtracking (constraint backtracking — open/close counts)
- **Difficulty:** Medium
- **Pattern:** constraint backtracking — `open < n` হলে `(`, `close < open` হলে `)`
- **Basic idea inherited from:** Subsets branching + validity pruning

</div>

## প্রশ্ন ও উদাহরণ {#problem}

### সহজ করে প্রশ্ন {#1-problem-in-simple-words}

একটা সংখ্যা `n` দেওয়া আছে — মানে `n` জোড়া বন্ধনী (`(` আর `)`)। তোমার কাজ: এদের দিয়ে গড়া **সব বৈধ (well-formed) সাজানো** বের করা — যেখানে প্রতিটা `(` ঠিকঠাক একটা `)` দিয়ে বন্ধ হয় আর কখনো `)` তার জোড়া `(`-এর আগে আসে না। সব রকম `2n`-অক্ষরের string নয়, শুধু **balanced** গুলো।

```text
n = 3
valid = ((())), (()()), (())(), ()(()), ()()()   (মোট 5 = Catalan(3))
```

### Input ও output {#8-example-input-and-output}

```text
Input : n=3 -> Output: ((())), (()()), (())(), ()(()), ()()()   (5টা)
Input : n=2 -> Output: (()), ()()                                (2টা)

Edge case 1 (এক জোড়া): n=1 -> Output: ["()"]
Edge case 2 (শূন্য):     n=0 -> Output: [""]   (খালি string-ই একমাত্র বৈধ)
```

### চেনা উদাহরণে বোঝা {#6-real-life-analogy}

একটা বইয়ের বন্ধনী/কোটেশন খোলা-বন্ধের কথা ভাবো: তুমি একটা নতুন বন্ধনী **খুলতে** পারো যদি কোটা শেষ না হয়, আর একটা **বন্ধ** করতে পারো শুধু যদি এমন একটা খোলা বন্ধনী থাকে যেটা এখনো বন্ধ হয়নি। কখনো এমন `)` লেখো না যার কোনো খোলা জোড়া নেই — ঠিক `close < open` নিয়ম। সব বৈধ লেখাই হলো সম্ভাব্য সব সাজ।

## ভিত্তির ধারণা {#idea}

### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}

ভিত্তি হলো **Subsets branching + validity pruning**। Subsets-এর মতো প্রতি position-এ branch (এখানে দুটো অক্ষর `(` বা `)`-এর পছন্দ)। কিন্তু সব `2^(2n)` string গড়ে শেষে যাচাই করার বদলে — **গড়ার সময়ই** নিয়ম মানি: শুধু তখনই `(` বসাই যখন আরও `(` বাকি, আর শুধু তখনই `)` বসাই যখন তার জন্য একটা খোলা `(` অপেক্ষায়। এই early validity check-ই pruning, যা Pattern 6-এর constraint backtracking-এর দিকে নিয়ে যায়।

### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}

লুকানো logic হলো **balance invariant**: যেকোনো prefix-এ `)`-এর সংখ্যা কখনো `(`-এর সংখ্যাকে ছাড়াবে না, আর শেষে দুটো সমান। এটাকে দুটো counter দিয়ে ধরি — `open` (বসানো `(`) আর `close` (বসানো `)`)। নিয়ম: `open < n` হলে আরও `(` দেওয়া যায়; `close < open` হলে একটা `)` দেওয়া যায়। বৈধ string-এর মোট সংখ্যা হলো **n-তম Catalan number** `C_n = (2n)! / ((n+1)!·n!)`।

### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}

একটা **list `path`** (অক্ষর জমিয়ে বর্তমান string গড়তে), একটা **list `out`** (সব বৈধ string জমাতে), দুটো **integer counter `open`/`close`**, আর recursion-এর জন্য **call stack**। leaf-এ `"".join(path)` দিয়ে string snapshot বানাই।

### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}

দুটো integer counter (`open`, `close`)-ই পুরো validity state ধরে রাখে — পুরো string পড়ে বারবার balance গোনার দরকার নেই, O(1)-তে সিদ্ধান্ত হয়। `path` mutable list বলে append/pop O(1), পুরো গাছ জুড়ে একটাই working string-buffer reuse হয়; `"".join` শুধু leaf-এ একবার। কোনো বৈধ string-ই হারায় না, কোনো অবৈধ-ও গড়া হয় না।

## ধাপে ধাপে সমাধান {#walkthrough}

### প্রথম সরল উপায় {#9-brute-force-thinking}

প্রথম সরল চিন্তা: `2n` দৈর্ঘ্যের প্রতিটা সম্ভাব্য `(`/`)` string গড়ো (`2^(2n)`টা), তারপর প্রতিটাকে balance-check করে শুধু বৈধগুলো রাখো।

```text
for s in all_strings_of_len_2n_over("()"):   # 2^(2n)
    if is_valid(s):                          # balance কখনো ঋণাত্মক নয়, শেষে 0
        out.append(s)
```

### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}

এই version `2^(2n)`টা string গড়ে — `n=3`-এ 64টা — অথচ বৈধ মাত্র 5টা (Catalan)। বিশাল সংখ্যাগরিষ্ঠ অবৈধ string গড়া হয়, তারপর প্রতিটায় O(n) balance-check। constraint backtracking অবৈধ branch-এ **ঢোকেই না**: `close < open` না হলে `)`-branch-টাই খোলা হয় না, তাই সরাসরি Catalan-সংখ্যক বৈধ string-ই গড়ে — গড়ার সময়ই বৈধতা, পরে filter নয়।

### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}

মূল observation: **বৈধতা একটা running balance দিয়েই পুরো ধরা যায়** — দুটো গণনা `open` আর `close`। যেকোনো মুহূর্তে দুটো প্রশ্ন: "আরও `(` দেওয়া যায়?" (হ্যাঁ যদি `open < n`) আর "একটা `)` দেওয়া যায়?" (হ্যাঁ যদি `close < open`)। এই দুটো শর্ত branch খোলার আগেই check করলে কোনো অবৈধ prefix কখনো তৈরিই হয় না।

### আরও কম কাজে সমাধান {#12-optimized-intuition}

`go(path, open, close)`: base case `len(path) == 2*n` হলে `"".join(path)` record। নাহলে দুটো শর্তসাপেক্ষ branch: যদি `open < n` → append `(`, `go(.., open+1, close)`, pop; যদি `close < open` → append `)`, `go(.., open, close+1)`, pop। শর্ত দুটোই branch-এ ঢোকার গেট — তাই কখনো অবৈধ অবস্থায় যাই না। এটাই early-validity constraint backtracking।

### ভাবনার পরিবর্তন {#13-thinking-tweak}

**মোচড়:** "সব string গড়ে কোনগুলো বৈধ?" ভেবো না; ভাবো "এই মুহূর্তে আইনসম্মতভাবে কোন অক্ষর বসাতে পারি?" — locally সর্বোচ্চ দুটো বৈধ পছন্দ, আর সেগুলোর গেট দুটো simple counter-তুলনা। validity-কে শেষের পরীক্ষা না বানিয়ে প্রতিটা step-এর শর্ত বানিয়ে দাও।

### ছবিতে বোঝা {#7-visual-explanation}

প্রতি step-এ ≤ 2 branch; `(` যদি `open<n`, `)` যদি `close<open`। `n = 2`-এর tree:

```text
                       go("", 0,0)
              ( (open<2)            ) (close<open? 0<0 না -> বন্ধ)
          go("(", 1,0)
        ( (open<2)        ) (close<open? 0<1 হ্যাঁ)
     go("((",2,0)      go("()",1,1)
       ) (1<2)            ( (open<2)
     go("(()",2,1)     go("()(",2,1)
       )                  )
     "(())"             "()()"

leaf (len == 2n) = 2 = Catalan(2) বৈধ string।
```

### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}

`generate_parenthesis(2)`, `go(path, open, close)`:

1. `go([],0,0)`: `open<2` → `(`; `go(['('],1,0)`। (`close<open`? 0<0 না, `)` branch নেই)
2. `go(['('],1,0)`: `open<2` → `((`: `go(['(','('],2,0)`; এছাড়া `close<open`(0<1) → `()`: `go(['(',')'],1,1)`।
3. `go(['(','('],2,0)`: `open<2` না; `close<open`(0<2) → `)`: `go("(()",2,1)` → আরও `)` → record `"(())"`।
4. `go(['(',')'],1,1)`: `open<2` → `()(`: পরে `)` → record `"()()"`।
5. out = `["(())", "()()"]` — 2টা।

## কোড ও ব্যাখ্যা {#code}

### Python {#15-python-solution}

```python
def generate_parenthesis(n):
    out = []
    def go(path, open_n, close_n):
        if len(path) == 2 * n:        # base case: 2n অক্ষর জমা
            out.append("".join(path)) # string snapshot
            return
        if open_n < n:                # আরও '(' দেওয়া বৈধ
            path.append("(")          # CHOOSE
            go(path, open_n + 1, close_n)   # EXPLORE
            path.pop()                # UN-CHOOSE
        if close_n < open_n:          # একটা খোলা '(' অপেক্ষায় -> ')' বৈধ
            path.append(")")          # CHOOSE
            go(path, open_n, close_n + 1)   # EXPLORE
            path.pop()                # UN-CHOOSE
    go([], 0, 0)
    return out

# ---- helper: বৈধতা যাচাই (test শক্ত করতে) ----
def is_valid(s):
    bal = 0
    for ch in s:
        bal += 1 if ch == "(" else -1
        if bal < 0:
            return False
    return bal == 0

# ---- tests (string-এর list -> বাইরের sort) ----
assert sorted(generate_parenthesis(3)) == sorted(
    ["((()))", "(()())", "(())()", "()(())", "()()()"])
assert sorted(generate_parenthesis(2)) == sorted(["(())", "()()"])
assert generate_parenthesis(1) == ["()"]
assert generate_parenthesis(0) == [""]          # খালি string-ই বৈধ
assert len(generate_parenthesis(4)) == 14        # Catalan(4)
assert all(is_valid(s) for s in generate_parenthesis(5))  # সবই balanced
print("সব test pass!")
```

### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}

- `if len(path) == 2 * n:` — base case: `2n` অক্ষর বসানো শেষ, একটা পূর্ণ বৈধ string।
- `out.append("".join(path))` — `path`-এর অক্ষর জুড়ে string snapshot record।
- `if open_n < n:` — এখনো `(` বাকি থাকলেই কেবল `(` বসাও।
- `path.append("("); go(.., open_n+1, ..); path.pop()` — choose → explore → un-choose, `open` বাড়াও।
- `if close_n < open_n:` — খোলা `(`-এর চেয়ে কম `)` থাকলেই `)` বৈধ (নাহলে balance ঋণাত্মক হতো)।
- `path.append(")"); go(.., close_n+1); path.pop()` — `)`-এর choose/explore/un-choose।

### Output মিলিয়ে দেখা {#17-output-walkthrough}

`generate_parenthesis(3)`: দুটো গেট (`open<n`, `close<open`) প্রতি step-এ কেবল বৈধ অক্ষরই বসাতে দেয়, তাই কোনো অবৈধ prefix জন্মায় না; ফল ঠিক 5টা (Catalan(3))। output string-এর list, ভেতরে অক্ষর-ক্রম জরুরি, তাই **বাইরের** list sort করে তুলনা (sorted) — assert stable অথচ সঠিক। `n=0`-এ `[""]`, `n=4`-এ 14, আর `is_valid` দিয়ে সবগুলো balanced যাচাই। সব মিলে print: `সব test pass!`।

### JavaScript ও test cases {#25-javascript-solution-with-test-cases}

```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function generateParenthesis(n) {
  const out = [];
  const go = (path, open, close) => {
    if (path.length === 2 * n) {        // base case: 2n অক্ষর জমা
      out.push(path.join(""));          // string snapshot
      return;
    }
    if (open < n) {                     // আরও '(' দেওয়া বৈধ
      path.push("(");                   // CHOOSE
      go(path, open + 1, close);        // EXPLORE
      path.pop();                       // UN-CHOOSE
    }
    if (close < open) {                 // একটা খোলা '(' অপেক্ষায় -> ')' বৈধ
      path.push(")");
      go(path, open, close + 1);
      path.pop();
    }
  };
  go([], 0, 0);
  return out;
}

// ---- helper: বৈধতা যাচাই (test শক্ত করতে) ----
const isValid = (s) => {
  let bal = 0;
  for (const ch of s) { bal += ch === "(" ? 1 : -1; if (bal < 0) return false; }
  return bal === 0;
};

// ---- test cases ----
assert(JSON.stringify(generateParenthesis(3).sort()) === JSON.stringify(["((()))", "(()())", "(())()", "()(())", "()()()"].sort()), "n=3");
assert(JSON.stringify(generateParenthesis(2).sort()) === JSON.stringify(["(())", "()()"].sort()), "n=2");
assert(JSON.stringify(generateParenthesis(1)) === JSON.stringify(["()"]), "n=1");
assert(JSON.stringify(generateParenthesis(0)) === JSON.stringify([""]), "n=0 -> ['']");
assert(generateParenthesis(4).length === 14, "Catalan(4)");
assert(generateParenthesis(5).every(isValid), "সবই balanced");
console.log("সব JS test pass!");
```
> **JS টীকা:** মূল চাবি — দুটো গেট: `open < n` হলে তবেই `(`, আর `close < open` হলে তবেই `)`। এই early-validity check-এর কারণে কোনো অবৈধ string জন্মায়ই না, শেষে filter করতে হয় না। `path.join("")` দিয়ে অক্ষর-array থেকে string snapshot বানাই (leaf-এ একবার)। সাবধান: `close < open` লেখো, ভুলে `close < n` নয় — নাহলে `")("`-এর মতো balance-ঋণাত্মক string আসবে।

### TypeScript ও test cases {#26-typescript-solution-with-test-cases}

```typescript
function generateParenthesis(n: number): string[] {
  const out: string[] = [];
  const go = (path: string[], open: number, close: number): void => {
    if (path.length === 2 * n) {
      out.push(path.join(""));          // string snapshot
      return;
    }
    if (open < n) {                     // '(' গেট
      path.push("(");
      go(path, open + 1, close);
      path.pop();
    }
    if (close < open) {                 // ')' গেট
      path.push(")");
      go(path, open, close + 1);
      path.pop();
    }
  };
  go([], 0, 0);
  return out;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const isValid = (s: string): boolean => {
  let bal = 0;
  for (const ch of s) { bal += ch === "(" ? 1 : -1; if (bal < 0) return false; }
  return bal === 0;
};

expect(JSON.stringify(generateParenthesis(3).sort()), JSON.stringify(["((()))", "(()())", "(())()", "()(())", "()()()"].sort()), "n3");
expect(JSON.stringify(generateParenthesis(2).sort()), JSON.stringify(["(())", "()()"].sort()), "n2");
expect(JSON.stringify(generateParenthesis(0)), JSON.stringify([""]), "n0");
expect(generateParenthesis(4).length, 14, "catalan4");
expect(generateParenthesis(5).every(isValid), true, "valid");
console.log("সব TS test pass!");
```
> **TS টীকা:** return type `string[]` স্পষ্ট করে output বৈধ string-এর list। `path: string[]` হলো অক্ষর জমানোর mutable buffer, `open`/`close: number` দুটো counter পুরো validity-state O(1)-তে ধরে রাখে — পুরো string পড়ে balance গুনতে হয় না। `go(...): void` signature বলে recursion শুধু `out`-এ side-effect করে; টাইপগুলো constraint-backtracking-এর state (buffer + দুই counter) পরিষ্কার রাখে।

## খরচ ও সাধারণ ভুল {#cost}

### সময় {#18-time-complexity}

**O(Cₙ · n)** — Cₙ হলো n-তম Catalan number (বৈধ string-সংখ্যা), প্রতিটার join-এ O(n)। asymptotic-এ Cₙ ≈ 4ⁿ / (n^1.5 √π) — exponential কিন্তু `2^(2n)` brute force-এর চেয়ে অনেক ছোট।

### অতিরিক্ত জায়গা {#19-space-complexity}

Output বাদ দিলে **O(n)** — `path` ও call stack-এর গভীরতা `2n`। Output ধরলে **O(Cₙ · n)**।

### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}

- দুটো গেট ছাড়া সব `(`/`)` চেষ্টা করা — অবৈধ string জন্মায়, শেষে filter করতে হয়; পুরো লাভ মাটি।
- `close < open`-এর বদলে `close < n` লেখা — তখন `)` বেশি বসে balance ঋণাত্মক হয় (যেমন `")("`)।
- `path.pop()` ভুলে যাওয়া — পরের branch-এ আগের অক্ষর leak করে।
- `"".join(path)`-এর বদলে `path` (list) record করা — সব entry একই live list।

## শেখা ও পরের অনুশীলন {#practice}

### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}

ভিত্তি: Subsets (#7)-এর branching, এখানে প্রতি branch-এর আগে validity গেট। [../patterns.md](../patterns.md)-এর Pattern 6 (Constraint backtracking)-এর মূল ভাব — "validate করো তাড়াতাড়ি, পুরো candidate বানিয়ে শেষে নয়।" এটা N-Queens (#19)-এর দিকে সহজ সেতু: ওখানেও প্রতি placement-এর আগে safe-check।

### পরের অনুশীলন {#22-similar-harder-problems}

- Palindrome Partitioning (cut-point + validity) — <https://leetcode.com/problems/palindrome-partitioning/> (এই tracker-এর #16)
- N-Queens (constraint backtracking) — <https://leetcode.com/problems/n-queens/> (#19)
- Letter Combinations (k-way branch) — <https://leetcode.com/problems/letter-combinations-of-a-phone-number/> (#8)

### কৌশলটি মনে রাখুন {#23-pattern-learned}

**Constraint backtracking with running counters:** validity-কে দুটো (বা কয়েকটা) integer counter দিয়ে track করো, আর প্রতিটা branch খোলার **আগে** শর্ত যাচাই করো (`open < n`, `close < open`); এতে অবৈধ অবস্থা কখনো তৈরি হয় না — generate-and-filter নয়, generate-only-valid।

### নিজেকে যাচাই করুন {#24-final-summary}

ভবিষ্যতের আমাকে: "Generate Parentheses = দুটো counter open/close; `open<n` হলে `(`, `close<open` হলে `)`; base case `len==2n`।" যখনই 'সব বৈধ গঠন গড়ো, validity শর্তে বাঁধা' শুনবে — এই early-validity constraint backtracking মনে করবে; বৈধতাকে শেষের test নয়, প্রতি step-এর গেট বানাও।

### কোথায় কাজে লাগে {#27-real-world-use}

- **Syntax/expression generation:** বৈধ বন্ধনী-গঠন, balanced tag/quote — parser ও code-generator টেস্টিং-এ।
- **Constraint backtracking শেখা:** "validity শর্তে বাঁধা সব গঠন গড়ো" — N-Queens, Sudoku-র দিকে সেতু।
- **Tree/structure enumeration:** n জোড়া বন্ধনী ↔ binary tree shape (Catalan) — সব আকৃতি enumerate করতে।
- **Combinatorial test generation:** নিয়ম-মানা সব বৈধ ইনপুট-গঠন তৈরি করে edge-case coverage।
- **Template/DSL validation:** nested structure-এর সব বৈধ বিন্যাস তৈরি বা যাচাই করতে।

এক কথায়, "validity শর্ত মেনে সব বৈধ গঠন গড়ো" শুনলেই — running counter দিয়ে validity track করে প্রতি branch খোলার **আগে** শর্ত যাচাই (generate-only-valid, filter নয়); এটাই constraint-backtracking-এর মূল।

---

> **মনে রাখার নিয়ম (legal):** সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।