Problem link ও উৎস
- **Original source:** LeetCode Pascal's Triangle
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Medium
- **Pattern:** DP-style build (Pascal's rule / additive nCr)
- **Basic idea inherited from:** 041 — Combination Basic (একই nCr, ভিন্ন পথ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো জিনিস চাই:
1. **Pascal's triangle**-এর প্রথম কয়েকটা সারি বানানো। এটা এমন একটা ত্রিভুজ যেখানে প্রতিটা ঘর হলো তার ঠিক উপরের দুই ঘরের যোগ, আর দুই ধার সবসময় 1।
2. সেই ত্রিভুজ থেকে `C(n, r)` পড়া — **কোনো গুণ বা ভাগ ছাড়াই**, শুধু যোগ করে।
মূল মজা: ত্রিভুজের n-তম সারির r-তম ঘর = ঠিক `C(n, r)`। মানে combination হিসাব করতে factorial-ও লাগে না, ভাগও লাগে না — শুধু যোগ।
### Input ও output {#6-example-input-and-output}
```text
generate(5) -> পুরো triangle (প্রথম 5 সারি):
[
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]
nCr_pascal(n, r) -> একক মান:
(5, 2) -> 10
(5, 0) -> 1
(6, 3) -> 20
(4, 4) -> 1
(4, 5) -> 0 (r > n -> ঘর নেই)
```
Edge case: দুই ধার (`r = 0` আর `r = n`) সবসময় 1; `r > n` হলে ত্রিভুজে সে ঘর নেই, তাই 0।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পিন-বোর্ডে (Galton board) উপর থেকে একটা বল ফেলছ। প্রতিটা পিন-এ বল হয় বাঁয়ে যায়, নয় ডানে।
- একদম উপরের ঘরে পৌঁছানোর 1 উপায় (শুরু)।
- নিচের যেকোনো ঘরে পৌঁছাতে হলে বলটা তার ঠিক উপরের বাঁ-ঘর বা ডান-ঘর থেকে নামতে হবে।
- তাই কোনো ঘরে পৌঁছানোর উপায়-সংখ্যা = উপরের দুই ঘরের উপায়-সংখ্যার **যোগ**।
এই উপায়-সংখ্যাগুলো বসালেই — হুবহু Pascal's triangle! আর n ধাপে r বার ডানে যাওয়ার উপায় = `C(n, r)`। তাই triangle আর "কয়টা path" একই জিনিস।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **041 (Combination Basic)**-এরই অন্য রূপ। 041-এ nCr বের করেছিলাম গুণ-ভাগ দিয়ে (`n!/(r!(n−r)!)`)। এখানে একই nCr, কিন্তু **recursive যোগের** পথে।
কেন দরকার এই দ্বিতীয় পথ?
- factorial বা বিশাল মাঝসংখ্যা লাগে না — শুধু ছোট ছোট যোগ
- অনেক nCr একসাথে লাগলে পুরো triangle একবার বানিয়ে সব O(1)-এ পড়া যায়
- **এটাই DP-র হাতেখড়ি** — বড় উত্তর ছোট উত্তর থেকে, table-এ জমিয়ে
আর এই additive idea পরে counting DP (coin change, path counting) — সবখানে ফিরবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea **Pascal's rule**:
```text
C(n, r) = C(n−1, r−1) + C(n−1, r)
```
গল্পটা সুন্দর: n জন থেকে r জন বাছছ। শেষ জনের (ধরো রিমা) দিকে তাকাও — দুটো সম্ভাবনা:
- **রিমা দলে আছে** → বাকি n−1 জন থেকে আরও r−1 জন বাছতে হবে → `C(n−1, r−1)`
- **রিমা দলে নেই** → বাকি n−1 জন থেকেই পুরো r জন বাছতে হবে → `C(n−1, r)`
দুটো ক্ষেত্র আলাদা ("অথবা"), তাই **যোগ**। এটাই triangle-এর "উপরের দুই ঘরের যোগ" নিয়ম।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি — Pascal's rule সরাসরি **recursion**-এ লেখা:
```python
def nCr_rec(n, r):
if r == 0 or r == n: # দুই ধার = 1
return 1
if r < 0 or r > n:
return 0
return nCr_rec(n - 1, r - 1) + nCr_rec(n - 1, r)
```
এটা সংজ্ঞার হুবহু অনুবাদ — "শেষ জন আছে নাকি নেই" দুই শাখার যোগ। ছোট n-এ একদম ঠিক উত্তর দেয়, আর গল্পটা সবচেয়ে পরিষ্কার দেখায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা হলো এই recursion **একই উপ-সমস্যা বারবার** হিসাব করে। যেমন `nCr_rec(5, 2)` ডাকতে গিয়ে `nCr_rec(3, 1)` বহুবার আলাদা শাখায় ফিরে আসে:
```text
nCr_rec(5,2) তলায় গেলে একই (3,1), (2,1) বারবার গণনা হয়
গাছটা প্রায় দ্বিগুণ হারে ফুলে ওঠে -> O(2^n) মতো
n = 30 হলেই কোটি কোটি বার call -> Time Limit Exceeded
```
ঠিক Fibonacci-র মতো — overlapping subproblem। এটাই DP-র দরজা: একবার হিসাব করো, জমিয়ে রাখো, আবার লাগলে পড়ে নাও।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: একই উপ-সমস্যা বারবার না করে, **নিচ থেকে উপরে (bottom-up) পুরো triangle একবার বানাও** — প্রতিটা সারি আগের সারি থেকে:
```python
def generate(num_rows):
triangle = []
for n in range(num_rows):
row = [1] * (n + 1) # দুই ধার আর জায়গা ভরা
for r in range(1, n): # ভেতরের ঘর গুলো
row[r] = triangle[n - 1][r - 1] + triangle[n - 1][r]
triangle.append(row)
return triangle
```
প্রতিটা ভেতরের ঘর আগের সারির দুই ঘরের যোগ। একবার বানিয়ে নিলে যেকোনো `C(n, r)` সাথে সাথে `triangle[n][r]` থেকে পড়া যায় — O(1)। এটাই **tabulation (DP)**।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **recursion-এর গাছটাকে উল্টে দাও — নিচ থেকে উপরে টেবিল ভরো।**
Recursion বড় থেকে ছোটতে নামে আর একই ছোট বারবার হিসাব করে। তার বদলে ছোট থেকে শুরু করো (row 0 = [1]), প্রতিটা নতুন সারি আগেরটা দেখে এক pass-এ বানাও। প্রতিটা উপ-উত্তর **ঠিক একবার** হিসাব হয়, table-এ থাকে।
এই "overlapping subproblem দেখলেই table বানাও" মোচড়টাই DP-র প্রাণ — Pascal triangle তার সবচেয়ে মিষ্টি প্রথম উদাহরণ।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো ত্রিভুজটা কীভাবে যোগ করে বানানো হয়:
```text
row 0: 1
row 1: 1 1
row 2: 1 2 1 (2 = 1 + 1)
row 3: 1 3 3 1 (3 = 1 + 2, আবার 3 = 2 + 1)
row 4: 1 4 6 4 1 (6 = 3 + 3)
row 5: 1 5 10 10 5 1 (10 = 4 + 6)
^
প্রতিটা ভেতরের ঘর = মাথার উপরের দুই ঘরের যোগ
```
এবার দেখো কোথায় কোন nCr লুকিয়ে — row n, position r:
```text
row 5: 1 5 10 10 5 1
position: 0 1 2 3 4 5
| | | | | |
C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5)
1 5 10 10 5 1
C(5,2) = 10 <- 5-তম সারির 2-তম ঘর ✓
দুই ধার সবসময় 1 = C(n,0) = C(n,n)
```
লক্ষ করো — কোনো গুণ-ভাগ নেই, শুধু পাশাপাশি ঘরের যোগ। আর প্রতিটা সারি বাম-ডান প্রতিসম (symmetry)।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `generate(4)` চালাই — সারি একটা একটা করে:
| n | শুরুর row | ভেতরের ঘর হিসাব | পূর্ণ row |
| --- | --- | --- | --- |
| 0 | [1] | — | [1] |
| 1 | [1, 1] | — (ভেতর নেই) | [1, 1] |
| 2 | [1, 1, 1] | row[1] = 1+1 = 2 | [1, 2, 1] |
| 3 | [1, 1, 1, 1] | row[1]=1+2=3, row[2]=2+1=3 | [1, 3, 3, 1] |
শেষ ত্রিভুজ: `[[1],[1,1],[1,2,1],[1,3,3,1]]`।
এবার `C(3, 1)` পড়তে চাইলে → `triangle[3][1] = 3` ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def generate(num_rows):
"""Pascal's triangle-এর প্রথম num_rows সারি বানায়।"""
triangle = []
for n in range(num_rows):
row = [1] * (n + 1)
for r in range(1, n): # ভেতরের ঘর
row[r] = triangle[n - 1][r - 1] + triangle[n - 1][r]
triangle.append(row)
return triangle
def nCr_pascal(n, r):
"""C(n, r) — Pascal's rule দিয়ে, কোনো ভাগ ছাড়া (শুধু যোগ)।"""
if r < 0 or r > n:
return 0
# n-তম সারি পর্যন্ত বানিয়ে r-তম ঘর পড়ি
prev = [1]
for _ in range(n):
cur = [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
prev = cur
return prev[r]
# --- ছোট test গুলো (সব pass করা উচিত) ---
import math
# generate ঠিক ত্রিভুজ দেয় কিনা
assert generate(1) == [[1]]
assert generate(5) == [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
]
# প্রতিটা ঘর = উপরের দুই ঘরের যোগ (নিজে যাচাই)
tri = generate(12)
for n in range(2, 12):
for r in range(1, n):
assert tri[n][r] == tri[n - 1][r - 1] + tri[n - 1][r]
# nCr_pascal == math.comb (পুরো triangle 0..12)
for n in range(0, 13):
for r in range(0, n + 1):
assert nCr_pascal(n, r) == math.comb(n, r)
assert nCr_pascal(5, 2) == 10
assert nCr_pascal(6, 3) == 20
assert nCr_pascal(4, 5) == 0 # r > n
assert nCr_pascal(7, 0) == 1 # ধার
# প্রতি সারির যোগফল = 2^n (বোনাস সত্য)
for n in range(0, 12):
assert sum(tri[n]) == 2 ** n
print(generate(4)) # [[1],[1,1],[1,2,1],[1,3,3,1]]
print(nCr_pascal(5, 2)) # 10
print(nCr_pascal(6, 3)) # 20
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def generate(num_rows):
triangle = []
for n in range(num_rows):
row = [1] * (n + 1)
```
প্রতিটা নতুন সারি শুরু করি সব 1 দিয়ে (n+1 টা ঘর) — তাতে দুই ধার এমনিতেই 1 হয়ে যায়।
```text
for r in range(1, n):
row[r] = triangle[n - 1][r - 1] + triangle[n - 1][r]
```
শুধু ভেতরের ঘরগুলো (1 থেকে n−1) আগের সারির দুই ঘরের যোগ দিয়ে ভরি। এটাই Pascal's rule।
```text
def nCr_pascal(n, r):
...
prev = [1]
for _ in range(n):
cur = [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
prev = cur
return prev[r]
```
একক `C(n, r)` চাইলে পুরো ত্রিভুজ না রেখে শুধু **আগের সারিটা** রাখি (memory বাঁচাতে), n বার নতুন সারি বানাই, শেষে r-তম ঘর পড়ি।
বাকি `assert` লাইনগুলো ত্রিভুজের গঠন, `math.comb`-এর সাথে মিল, আর "সারির যোগ = 2ⁿ" — সব দিক যাচাই করছে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
10
20
সব test pass!
```
প্রথম লাইন `generate(4)`-এর ত্রিভুজ। পরের দুই লাইন `nCr_pascal(5,2)` = 10, `nCr_pascal(6,3)` = 20। তার আগের সব `assert` (গঠন, `math.comb`, 2ⁿ — সব cross-check) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
পুরো triangle (n সারি) বানাতে **O(n²)** — মোট ঘর-সংখ্যা 1+2+...+n ≈ n²/2, প্রতিটা একবার যোগ। একক `nCr_pascal(n, r)`-ও O(n²) (n সারি, প্রতিটা পর্যন্ত O(n) কাজ)।
(তুলনায়: 041-এর সরাসরি গুণ-ভাগ একক nCr-এ O(r) — দ্রুত। কিন্তু **অনেক** nCr একসাথে লাগলে একবার triangle বানিয়ে সব O(1)-এ পড়া লাভজনক।)
### অতিরিক্ত জায়গা {#16-space-complexity}
পুরো triangle রাখলে **O(n²)**। একটা একক `C(n, r)`-এর জন্য শুধু আগের সারি রাখলে **O(n)** (`nCr_pascal`-এ ঠিক তাই করেছি)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **Naive recursion ব্যবহার করা** — overlapping subproblem-এ O(2ⁿ); table বানাও বা memoize করো।
2. **দুই ধার ভুলে যাওয়া** — প্রতি সারির প্রথম ও শেষ ঘর সবসময় 1; না বসালে যোগ ভুল হবে।
3. **Index গুলিয়ে ফেলা** — row n-এর ঘর 0 থেকে n পর্যন্ত (n+1 টা); `C(n, r)` = `triangle[n][r]`, off-by-one সাবধান।
4. **`r > n`-এ crash** — ত্রিভুজে সে ঘর নেই; আগে 0 ফেরত দাও।
5. **বড় n-এ এটাই দ্রুততম ভাবা** — একক nCr-এ 041-এর O(r) গুণ-ভাগ দ্রুত; Pascal লাভজনক যখন অনেক মান একসাথে চাই।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Pascal's Triangle II** (