015 — Generate Parentheses

Source

• 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

1. Problem in simple words

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

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

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-ই হারায় না, কোনো অবৈধ-ও গড়া হয় না।

6. Real-life analogy

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

7. Visual explanation

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

                       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।

8. Example input and output

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

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

9. Brute force thinking

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

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-এর শর্ত বানিয়ে দাও।

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টা।

15. Python solution

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।

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!।

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।

21. Which basic problem this inherits from

ভিত্তি: Subsets (#7)-এর branching, এখানে প্রতি branch-এর আগে validity গেট। ../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-এর গেট বানাও।

25. JavaScript solution (with test cases)

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 আসবে।

26. TypeScript solution (with test cases)

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) পরিষ্কার রাখে।

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।