Problem link ও উৎস
- **Original source:** Classic backtracking exercise (partition into palindromes)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (cut-point backtracking)
- **Difficulty:** Medium
- **Pattern:** cut-point backtracking — প্রতি cut-এ palindrome হলে এগোও, নাহলে বাদ
- **Basic idea inherited from:** Combinations (cut position-গুলোই choice)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` দেওয়া আছে। তোমার কাজ: একে এমনভাবে টুকরো করা (partition করা) যেন **প্রতিটা টুকরোই palindrome** (উল্টে পড়লেও একই) — আর এমন সব সম্ভাব্য টুকরো-করা বের করা। মূল string-এর অক্ষর-ক্রম বদলায় না, শুধু কোথায় কোথায় "কাটছ" সেটাই পছন্দ। প্রতিটা partition একটা টুকরোর তালিকা।
```text
s = "aab"
partitions = ["a","a","b"], ["aa","b"] ("aab" নিজে palindrome নয়, তাই পুরোটা এক টুকরো হয় না)
```
### Input ও output {#8-example-input-and-output}
```text
Input : "aab" -> Output: ["a","a","b"], ["aa","b"]
Input : "aba" -> Output: ["a","b","a"], ["aba"]
Edge case 1 (এক অক্ষর): "a" -> Output: [["a"]]
Edge case 2 (সব সমান): "aa" -> Output: ["a","a"], ["aa"]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা লম্বা পুঁতির মালা ভাবো, যেটা তুমি কয়েক টুকরোয় কাটতে চাও — কিন্তু শর্ত: প্রতিটা টুকরোর পুঁতির নকশা দুদিক থেকে একই রকম (symmetric) হতে হবে। তুমি বাঁ-প্রান্ত থেকে শুরু করে একটা symmetric টুকরো কাটো, তারপর বাকি মালার জন্য একই কাজ করো। সব রকম বৈধ কাটাই হলো সব partition।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Combinations — cut position-গুলোই choice**। Combinations-এ আমরা index বাছতাম; এখানে বাছি **কোথায় কাটব**। একটা start position থেকে প্রতিটা সম্ভাব্য শেষ position পর্যন্ত একটা টুকরো ভাবি; টুকরোটা palindrome হলে সেটা নিয়ে বাকি string-এর জন্য recurse করি (start = ওই টুকরোর পরে)। start-index দিয়ে সবসময় সামনে এগোনো — combinations-এর সেই কঙ্কাল, এখন cut-point-এর ভাষায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **`n`-অক্ষরের string-এ `n-1`টা সম্ভাব্য cut-গাপ**, প্রতিটায় কাটা/না-কাটা দুই পছন্দ — মানে সর্বোচ্চ `2^(n-1)` রকম partition। কিন্তু palindrome শর্ত বেশিরভাগ partition বাতিল করে (validity pruning)। প্রতিটা recursive call একটা বৈধ palindrome prefix নেয়, তারপর "বাকি suffix কীভাবে partition হবে" — একই সমস্যা, ছোট string-এ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান partition-এর টুকরোগুলো), একটা **list `out`** (সব partition জমাতে), একটা **integer `start`** (পরবর্তী টুকরো কোথা থেকে), একটা **palindrome-check helper**, আর recursion-এর জন্য **call stack**। record-এ `path[:]` snapshot।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`start` integer-টা বলে দেয় suffix কোথা থেকে শুরু — তাই প্রতিটা partition বাঁ-থেকে-ডান একটাই ক্রমে গড়ে, পুনরাবৃত্তি নেই (combinations-এর start-index ভূমিকা)। `path` mutable বলে টুকরো append/pop O(1)। palindrome-check `sub == sub[::-1]` সরল ও O(length); চাইলে এটাকে precompute (DP table) দিয়ে দ্রুত করা যায় — সেটাই memoization → DP-র দিকে ইশারা।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `n-1`টা cut-গাপের প্রতিটায় কাটা/না-কাটা — সব `2^(n-1)` রকম partition গড়ো, তারপর যে partition-এর **সব** টুকরো palindrome শুধু সেগুলো রাখো।
```text
for each subset of cut positions (2^(n-1)):
pieces = split s at those cuts
if all(p == p[::-1] for p in pieces):
out.append(pieces)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version সবসময় পুরো `2^(n-1)`টা partition গড়ে, তারপর প্রতিটার প্রতিটা টুকরো palindrome কিনা যাচাই করে — অধিকাংশই প্রথম non-palindrome টুকরোতেই বাতিল, কিন্তু গড়া হয়ে যাওয়ার পরে। অপচয়: একটা prefix অলরেডি non-palindrome জানা সত্ত্বেও তার পরের সব cut-সমন্বয় গড়া হয়। backtracking যে মুহূর্তে একটা টুকরো non-palindrome, সেই branch-এ **আর নামেই না** — তাই hopeless subtree গাছেই কাটা পড়ে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা সিদ্ধান্ত হলো "পরের টুকরো কোথায় শেষ হবে"**, আর সেই টুকরো palindrome হলে তবেই বৈধ branch। "সব partition কী?" না ভেবে ভাবো "এই start থেকে একটা বৈধ (palindrome) prefix কতদূর হতে পারে?" — প্রতিটা বৈধ prefix-এর জন্য বাকি suffix recursively partition হয়। validity-টা branch খোলার শর্ত, শেষের test নয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`go(start, path)`: base case `start == len(s)` হলে snapshot record (পুরো string ঢাকা পড়েছে)। নাহলে `end` `start+1` থেকে `len(s)` পর্যন্ত: `piece = s[start:end]`; যদি `piece` palindrome হয় → append (choose), `go(end, path)` (explore — পরের টুকরো `end` থেকে), pop (un-choose)। palindrome না হলে সেই `end` skip। start-index combinations + প্রতি cut-এ validity গেট।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোথায় কোথায় কাটব" — সব cut একসাথে ভেবো না; ভাবো "এই বাঁ-প্রান্ত থেকে একটা বৈধ palindrome টুকরো নিই, বাকিটা recursion সামলাক।" বড় partition-সমস্যাটা নেমে আসে "এক টুকরো বাছো, ছোট string-এ একই সমস্যা"-তে — Combinations-এর "এক item বাছো, এগোও"-এর হুবহু রূপ, শুধু item-এর জায়গায় palindrome prefix।
### ছবিতে বোঝা {#7-visual-explanation}
start থেকে প্রতিটা end চেষ্টা; piece palindrome হলেই recurse। `"aab"`-এর tree:
```text
go(0, [])
"a"(pal) / "aa"(pal) | "aab"(না-pal, বাদ)
go(1, ["a"]) go(2, ["aa"])
"a"(pal)| "b"(pal)|
go(2,["a","a"]) go(3,["aa","b"]) -> record ["aa","b"]
"b"(pal)|
go(3,["a","a","b"]) -> record ["a","a","b"]
start == len(s) -> record; piece palindrome না হলে সেই branch বাদ।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`partition("aab")`, `go(start, path)`:
1. `go(0,[])`: `end=1` `"a"` (pal): append → `go(1,["a"])`।
2. `go(1,["a"])`: `end=2` `"a"` (pal): append → `go(2,["a","a"])`।
3. `go(2,["a","a"])`: `end=3` `"b"` (pal): append → `go(3,["a","a","b"])`: `start==3` → record `["a","a","b"]`; pop চেইন।
4. `go(1,["a"])`: `end=3` `"ab"` (না-pal): skip; pop "a"।
5. `go(0,[])`: `end=2` `"aa"` (pal): append → `go(2,["aa"])`: `end=3` `"b"` (pal): record `["aa","b"]`। `end=3` `"aab"` (না-pal): skip।
6. out = `[["a","a","b"], ["aa","b"]]` — 2টা।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def partition(s):
out = []
def is_pal(sub):
return sub == sub[::-1] # উল্টো করে মিলিয়ে দেখা
def go(start, path):
if start == len(s): # base case: পুরো string ঢাকা পড়েছে
out.append(path[:]) # snapshot!
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if is_pal(piece): # validity গেট
path.append(piece) # CHOOSE
go(end, path) # EXPLORE (পরের টুকরো end থেকে)
path.pop() # UN-CHOOSE
go(0, [])
return out
# ---- order-independent তুলনার helper (টুকরোর ক্রম জরুরি) ----
def norm(list_of_lists):
return sorted(list_of_lists) # শুধু বাইরের list sort, টুকরোর ক্রম অটুট
# ---- tests ----
assert norm(partition("aab")) == norm([["a", "a", "b"], ["aa", "b"]])
assert norm(partition("aba")) == norm([["a", "b", "a"], ["aba"]])
assert partition("a") == [["a"]]
assert norm(partition("aa")) == norm([["a", "a"], ["aa"]])
assert len(partition("aab")) == 2
assert all(all(p == p[::-1] for p in part) for part in partition("aabb")) # সব টুকরো palindrome
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `def is_pal(sub): return sub == sub[::-1]` — টুকরোটা palindrome কিনা; `[::-1]` উল্টো করে।
- `if start == len(s):` — base case: পুরো string-ই টুকরোয় ঢাকা পড়েছে, একটা পূর্ণ partition।
- `out.append(path[:])` — snapshot; live `path` পরে বদলাবে।
- `for end in range(start+1, len(s)+1):` — `start` থেকে প্রতিটা সম্ভাব্য টুকরো-শেষ (cut position)।
- `if is_pal(piece):` — validity গেট: শুধু palindrome টুকরোর branch খোলো।
- `path.append(piece); go(end, path); path.pop()` — choose → explore (পরের টুকরো `end` থেকে) → un-choose।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`partition("aab")`: `start=0` থেকে `"a"` ও `"aa"` দুটোই palindrome, তাই দুটো শাখা; `"aab"` palindrome নয় বলে পুরোটা-একটুকরো branch বাদ। প্রথম শাখা `["a","a","b"]`, দ্বিতীয় `["aa","b"]`। ফল 2টা। partition-এ টুকরোর **ক্রম জরুরি** (`["a","a","b"]` একটা sequence), তাই `norm`-এ শুধু বাইরের list sort করি (sorted-of-sorted নয়) — assert stable অথচ সঠিক। `"a"`-তে 1টা, আর সব টুকরো palindrome যাচাই। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
worst case **O(n · 2^n)** — সর্বোচ্চ `2^(n-1)` partition (যেমন সব অক্ষর সমান), প্রতিটা গড়তে ও palindrome-check-এ O(n) পর্যন্ত। is-palindrome precompute করলে check অংশ O(1) করা যায়।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(n)** — call stack + `path`-এর গভীরতা n (প্রতি অক্ষর আলাদা টুকরো হলে)। Output ধরলে সব partition-এর মোট আকার।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- palindrome-check বাদ দিয়ে সব cut গড়ে শেষে filter করা — hopeless branch-এ নেমে অপচয়; গেটটা branch খোলার আগে দাও।
- `go(end)`-এর বদলে `go(end+1)` বা `go(start+1)` — হয় অক্ষর বাদ পড়ে, নয় টুকরো ঠিকমতো জোড়া লাগে না।
- `range(start+1, len(s)+1)`-এর `+1` ভুলে যাওয়া — শেষ অক্ষরের টুকরো বা শেষ end ধরা পড়ে না।
- `out.append(path)` snapshot ছাড়া — সব entry একই live list-এর reference।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Combinations (এই tracker-এর #11)-এর start-index — এখানে "item" বদলে "palindrome prefix"। [../patterns.md](../patterns.md)-এর Pattern 5 (start-index) + Pattern 6 (validity গেট) দুটোর মিশ্রণ। এটা Word Search (#17) বা cut-ভিত্তিক DP (যেমন Palindrome Partitioning II — min cuts) এর দিকে সেতু — সেখানে count/min চাইলে memoize করে [../../12-dynamic-programming/](../../12-dynamic-programming/README.md)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Generate Parentheses (constraint backtracking) —