Problem link ও উৎস
- **Original source:** Related — LeetCode Unique Binary Search Trees
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Medium
- **Pattern:** balanced structures (Catalan number)
- **Basic idea inherited from:** 048 — Count Paths in Grid (lattice path-এর বিশেষ রূপ → Catalan)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n`-তম **Catalan number**, লেখা `Cat(n)`, বের করতে হবে। এই সংখ্যা অনেক "balanced" গোছের জিনিস গোনে। সবচেয়ে সহজ গল্প — **balanced bracket**:
`n` জোড়া bracket (মানে n টা `(` আর n টা `)`) কত ভাবে **সঠিকভাবে** সাজানো যায়, যেন প্রতিটা `(`-এর জন্য পরে একটা মেলানো `)` থাকে আর কখনো `)`-এর সংখ্যা `(`-কে ছাড়িয়ে না যায়?
যেমন n=3: `()()()`, `(())()`, `()(())`, `(()())`, `((()))` — মোট 5টা। তাই `Cat(3) = 5`।
ধারা: `Cat(0)=1, Cat(1)=1, Cat(2)=2, Cat(3)=5, Cat(4)=14, ...`।
### Input ও output {#6-example-input-and-output}
```text
n -> Cat(n)
-------------
0 -> 1 (খালি -> 1 ভাবে, বিশেষ নিয়ম)
1 -> 1 "()"
2 -> 2 "()()", "(())"
3 -> 5
4 -> 14
5 -> 42
6 -> 132
10 -> 16796
```
Edge case: **Cat(0) = 1** (খালি bracket-সারির ঠিক একটা সাজানো — কিছু না; factorial-এর 0!=1-এর মতো)। ধারাটা দ্রুত বাড়ে কিন্তু 2ⁿ-এর চেয়ে ধীরে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো n জন মানুষ একটা সিনেমার টিকিট কিনছে, টিকিটের দাম 50 টাকা। অর্ধেকের (n জন) কাছে আছে 50 টাকার নোট, বাকি অর্ধেকের কাছে 100 টাকার। কাউন্টারে শুরুতে কোনো খুচরা নেই।
100-টাকার লোককে ফেরত দিতে হলে আগে একটা 50-টাকার নোট জমা থাকতে হবে। তাই লাইনে এমনভাবে দাঁড়াতে হবে যেন **যেকোনো মুহূর্তে জমা-হওয়া 50-নোটের সংখ্যা ≥ চাওয়া-ফেরতের সংখ্যা** — নাহলে কাউন্টার আটকে যাবে।
এই "কখনো ঘাটতি হবে না" শর্ত মানা লাইন কত রকম? — ঠিক `Cat(n)`! 50-নোট = `(`, 100-নোট = `)` ভাবলেই হুবহু balanced bracket। এই "কখনো নিচে নামবে না" চরিত্রই Catalan-এর সর্বত্র লুকিয়ে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **048 (Count Paths in Grid)**-এর উপর দাঁড়িয়ে। সেখানে শিখেছ grid path = R/D সাজানো = `C(m+n, n)`। Catalan হলো তারই একটা **বিশেষ, সীমাবদ্ধ রূপ**: এমন path যা কখনো diagonal পেরোয় না (অর্থাৎ সবসময় `)`-এর চেয়ে `(` সমান-বা-বেশি)।
মূল ধারাবাহিকতা: মোট path `C(2n, n)` (048-এর সরাসরি প্রয়োগ); তার থেকে নিয়ম-ভাঙা path বাদ দিলে `C(2n,n)/(n+1)`। তাই 048-এর nCr-চিন্তা না থাকলে Catalan-এর closed form-টাই দাঁড়ায় না। আর recurrence-এ "ভেতর × বাইর" multiplication principle (039-এর শিকড়)-এরই খেলা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো সমান চেহারা:
**বন্ধ-রূপ (closed form):**
```text
Cat(n) = C(2n, n) / (n + 1)
```
(সমান: `C(2n, n) − C(2n, n+1)`।) gridপথ-এর সাথে যোগ: 2n ধাপের মধ্যে diagonal না-পেরিয়ে যাওয়া path — মোট path `C(2n, n)` থেকে "নিয়ম-ভাঙা" বাদ দিলে এটাই।
**Recurrence (গল্প-রূপ):** প্রথম `(`-এর মেলানো `)` কোথায়, সেটা দিয়ে ভাগ করো — ভেতরে i জোড়া, বাইরে বাকি:
```text
Cat(n) = Σ (i=0..n−1) Cat(i) × Cat(n−1−i), Cat(0) = 1
```
দুটোই একই ধারা দেয়; closed form দ্রুত, recurrence গল্পটা বোঝায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি (আর গল্প-বোঝানো) — **সত্যিই সব bracket-সারি বানিয়ে valid-গুলো গোনা।** 2n জায়গায় প্রতিটায় `(` বা `)`, তারপর balanced কিনা চেক:
```python
from itertools import product
def is_balanced(s):
bal = 0
for ch in s:
bal += 1 if ch == '(' else -1
if bal < 0: # ')' বেশি হয়ে গেল -> invalid
return False
return bal == 0 # শেষে সমান
def catalan_brute(n):
if n == 0:
return 1
count = 0
for combo in product('()', repeat=2 * n):
if is_balanced(''.join(combo)):
count += 1
return count
```
প্রতিটা সম্ভাব্য সারি ঘুরে valid গুনি — ছোট n-এ একদম ঠিক, আর Catalan সংখ্যা চোখে যাচাইয়ের নিখুঁত উপায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা — 2n জায়গায় প্রতিটায় 2 রকম, মানে `2^(2n) = 4ⁿ` সারি ঘুরতে হয়, যার বেশিরভাগই invalid:
```text
n = 10 হলে: 4^10 ≈ 10^6 সারি -> চলে কিন্তু ভারী
n = 15 হলে: 4^15 ≈ 10^9 সারি -> অসম্ভব ধীর
closed form: C(2n, n)/(n+1) -> এক ধাপে, O(n)!
```
মোট valid সারিই Cat(n) (যা 4ⁿ-এর তুলনায় ছোট), কিন্তু সব 4ⁿ ঘুরে valid বাছা বিরাট অপচয় — formula সরাসরি উত্তর দেয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
দুটো ভালো পথ:
**পথ 1 — closed form (সবচেয়ে দ্রুত):**
```python
from math import comb
def catalan(n):
return comb(2 * n, n) // (n + 1)
```
`C(2n, n)` সবসময় `(n+1)` দিয়ে নিঃশেষে ভাগ যায় (Catalan-এর সুন্দর সত্য), তাই integer থাকে।
**পথ 2 — DP recurrence (গল্প জমানো, overlapping subproblem):**
```python
def catalan_dp(n):
cat = [0] * (n + 1)
cat[0] = 1
for k in range(1, n + 1):
cat[k] = sum(cat[i] * cat[k - 1 - i] for i in range(k))
return cat[n]
```
DP-তে ছোট Catalan জমিয়ে বড়টা বানাই — closed form না মনে থাকলেও এটা চলে, আর recurrence-এর গল্পটাই code।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **"একটা শর্ত যা কখনো ভাঙা যাবে না, শুরু থেকে শেষ পর্যন্ত balanced থাকতে হবে" — এই চরিত্র দেখলেই Catalan সন্দেহ করো।**
আর recurrence-এর tweak: **একটা স্বাভাবিক "প্রথম বিভাজন বিন্দু" খোঁজো** (প্রথম `(`-এর মেলানো `)`, বা root node) — সেটা সমস্যাটাকে দুটো ছোট একই-ধরনের সমস্যায় ভাগ করে, আর তাদের গুণ-যোগই recurrence। এই "প্রথম মেলানো জোড়া দিয়ে দুই ভাগ" চিন্তাটা পরে tree/bracket DP-তে বারবার ফিরবে — Catalan তার প্রথম আভাস।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো n=3-এর 5টা balanced bracket (কেন 5):
```text
n = 3 (3 টা '(' , 3 টা ')'):
()()() (())() ()(()) (()()) ((()))
\ /
সবগুলোতেই প্রতি ')' -এর আগে যথেষ্ট '(' আছে -> valid
মোট 5 = Cat(3)
```
এবার দেখো recurrence-এর গল্প (প্রথম `(`-এর জোড়া কোথায়):
```text
( A ) B -> A = ভেতরের balanced, B = বাইরের balanced
ভেতরে i জোড়া হলে বাইরে (n−1−i) জোড়া
Cat(3) = Cat(0)·Cat(2) + Cat(1)·Cat(1) + Cat(2)·Cat(0)
= 1 · 2 + 1 · 1 + 2 · 1
= 2 + 1 + 2 = 5 ✓
```
আর closed form: `Cat(3) = C(6,3)/4 = 20/4 = 5` ✓ — তিন পথ, এক উত্তর।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `catalan_dp(3)` চালাই (`cat[0]=1` থেকে শুরু):
| k | হিসাব (Σ cat[i]·cat[k−1−i]) | cat[k] |
| --- | --- | --- |
| 0 | — (শুরু) | 1 |
| 1 | cat[0]·cat[0] = 1·1 | 1 |
| 2 | cat[0]·cat[1] + cat[1]·cat[0] = 1+1 | 2 |
| 3 | cat[0]·cat[2] + cat[1]·cat[1] + cat[2]·cat[0] = 2+1+2 | 5 |
`cat[3] = 5` ✓।
closed form দিয়ে যাচাই: `C(6,3)/4 = 20/4 = 5` ✓। হাতে bracket-ও 5টা — তিন পথ মিলল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from math import comb
def catalan(n):
"""n-তম Catalan number (closed form): C(2n, n) / (n+1)।"""
return comb(2 * n, n) // (n + 1)
def catalan_dp(n):
"""একই সংখ্যা DP recurrence-এ: Cat(k) = Σ Cat(i)·Cat(k−1−i)।"""
cat = [0] * (n + 1)
cat[0] = 1
for k in range(1, n + 1):
cat[k] = sum(cat[i] * cat[k - 1 - i] for i in range(k))
return cat[n]
# --- brute force verifier (সব bracket-সারি বানিয়ে valid গোনা) ---
from itertools import product
def is_balanced(s):
bal = 0
for ch in s:
bal += 1 if ch == '(' else -1
if bal < 0:
return False
return bal == 0
def catalan_brute(n):
if n == 0:
return 1
count = 0
for combo in product('()', repeat=2 * n):
if is_balanced(''.join(combo)):
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
# জানা মান
known = [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
for n, val in enumerate(known):
assert catalan(n) == val
assert catalan_dp(n) == val
# closed form == DP (0..15 জুড়ে)
for n in range(0, 16):
assert catalan(n) == catalan_dp(n)
# closed form == brute force enumeration (ছোট n, 0..8)
for n in range(0, 9):
assert catalan(n) == catalan_brute(n)
# Cat(n) = C(2n,n) − C(2n,n+1) (বিকল্প রূপও মেলে)
for n in range(0, 12):
assert catalan(n) == comb(2 * n, n) - comb(2 * n, n + 1)
print(catalan(3)) # 5
print(catalan(5)) # 42
print(catalan_dp(4)) # 14
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def catalan(n):
return comb(2 * n, n) // (n + 1)
```
closed form — `C(2n, n)` গুনে `(n+1)` দিয়ে ভাগ। এই ভাগ সবসময় নিঃশেষ, তাই `//` integer রাখে।
```text
def catalan_dp(n):
cat = [0] * (n + 1)
cat[0] = 1
for k in range(1, n + 1):
cat[k] = sum(cat[i] * cat[k - 1 - i] for i in range(k))
```
DP — `cat[0]=1` থেকে শুরু; প্রতিটা `cat[k]` আগের সব মান থেকে recurrence দিয়ে (ভেতরে i জোড়া × বাইরে k−1−i জোড়া, সব i-তে যোগ)।
```text
def is_balanced(s):
bal = 0
for ch in s:
bal += 1 if ch == '(' else -1
if bal < 0: return False
return bal == 0
```
verify-র জন্য — `(` হলে +1, `)` হলে −1; কখনো negative হলে invalid (`)` বেশি), শেষে 0 হলে valid।
বাকি `assert` লাইনগুলো জানা মান, closed form vs DP, brute enumeration আর বিকল্প রূপ — চার দিক থেকে যাচাই করছে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
5
42
14
সব test pass!
```
প্রথম: `catalan(3)` = 5। দ্বিতীয়: `catalan(5)` = 42। তৃতীয়: `catalan_dp(4)` = 14। আগের সব `assert` (জানা মান, closed form = DP = brute = বিকল্প রূপ — চার দিক cross-check) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
closed form `catalan(n)` **O(n)** — একটা `C(2n, n)` হিসাব (n টা গুণ-ভাগ)। DP `catalan_dp(n)` **O(n²)** — প্রতিটা `cat[k]`-এ k টা পদ যোগ। brute **O(4ⁿ · n)** — exponential। closed form-ই দ্রুততম।
### অতিরিক্ত জায়গা {#16-space-complexity}
closed form **O(1)**। DP **O(n)** — পুরো `cat` array। brute **O(n)** — একটা সারি বানাতে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`(n+1)` দিয়ে ভাগ ভুলে যাওয়া** — `C(2n, n)`-ই Catalan নয়; `/(n+1)` লাগবেই।
2. **Cat(0) ভুল ভাবা** — `Cat(0) = 1` (খালি, ঠিক একভাবে), 0 নয়।
3. **Recurrence-এ index উল্টানো** — `Cat(i)·Cat(n−1−i)`, যোগফল i=0..n−1; সীমা ভুল হলে ধারা নষ্ট।
4. **brute force বড় n-এ চালানো** — 4ⁿ, n≈15-এই অচল; formula বা DP নাও।
5. **সব counting-কে Catalan ভাবা** — শুধু "কখনো-নিয়ম-ভাঙবে-না / balanced / recursively দুই ভাগ" চরিত্রেই Catalan; সাধারণ বাছাই combination।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Unique Binary Search Trees** (