Problem link ও উৎস
- **Original source:** Classic backtracking exercise (phone keypad)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (Cartesian choose-explore)
- **Difficulty:** Medium
- **Pattern:** Cartesian choose-explore — প্রতি digit-এ k-way branch
- **Basic idea inherited from:** Subsets branching, k-way
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
পুরোনো phone keypad-এ প্রতিটা digit-এর সাথে কিছু অক্ষর থাকে: `2 → abc`, `3 → def`, ... `9 → wxyz`। `"23"`-এর মতো একটা digit-string দেওয়া আছে। তোমার কাজ: প্রতিটা digit থেকে একটা করে অক্ষর নিয়ে গড়া **সব সম্ভাব্য word** বের করা। `"23"`-এ প্রথম digit থেকে `a/b/c`, দ্বিতীয় থেকে `d/e/f` — মোট 3×3 = 9টা word।
```text
"23" -> "ad","ae","af","bd","be","bf","cd","ce","cf" (3 × 3 = 9)
```
### Input ও output {#8-example-input-and-output}
```text
Input : "23" -> Output: ad,ae,af,bd,be,bf,cd,ce,cf (9টা)
Input : "2" -> Output: a, b, c
Edge case 1 (খালি): "" -> Output: [] (কোনো word নেই)
Edge case 2 (4-অক্ষর digit): "9" -> Output: w, x, y, z
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা combination lock-এর কথা ভাবো যেখানে প্রতিটা চাকতিতে আলাদা সংখ্যক অক্ষর। প্রথম চাকতিতে একটা অক্ষর বাছো, তারপর দ্বিতীয়টায় প্রতিটা অক্ষর ঘুরিয়ে দেখো, তারপর তৃতীয়টায়... প্রথম চাকতির প্রতিটা পছন্দের জন্য বাকি চাকতির সব সংমিশ্রণ ঘোরে। সব চাকতির সব সমন্বয়ই হলো সম্ভাব্য সব word।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Subsets branching, k-way**। Subsets-এ প্রতিটা item-এ ঠিক 2টা branch (include/exclude) ছিল। এখানে প্রতিটা digit-এ branch-এর সংখ্যা = ওই digit-এর অক্ষরসংখ্যা (3 বা 4)। অর্থাৎ fixed-2 branching-এর বদলে **k-way branching** — কিন্তু কঙ্কালটা একই choose → explore → un-choose।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো math হলো **Cartesian product**: digit-গুলোর অক্ষর-সেটের সব সম্ভাব্য সংমিশ্রণ। `"23"` মানে `{a,b,c} × {d,e,f}`। মোট word-সংখ্যা = প্রতিটা digit-এর অক্ষরসংখ্যার গুণফল (rule of product)। প্রতিটা leaf-এ ঠিক digit-সংখ্যার সমান লম্বা একটা word তৈরি হয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **dict (hash map)** digit → অক্ষর mapping রাখতে; একটা **list `path`** (বর্তমান word গড়তে); একটা **list `out`** (সব word জমাতে); আর recursion-এর জন্য **call stack**। mapping lookup O(1) বলে dict নিখুঁত।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
dict দিয়ে `digits[i]` → তার অক্ষরগুলো O(1)-তে পাওয়া যায়, তাই প্রতি level-এ branching options সঙ্গে সঙ্গে হাতে আসে — এটাই hash-map lookup pattern। আর `path` একটা mutable list বলে append/pop O(1), পুরো decision-tree জুড়ে একটাই word-buffer reuse করা যায়; leaf-এ `"".join(path)` দিয়ে snapshot বানাই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: nested loop — যত digit তত loop, প্রতিটা loop ওই digit-এর অক্ষরের উপর; ভেতরের সব loop মিলে word গড়ো।
```text
for c1 in letters[d1]:
for c2 in letters[d2]:
... (digit যত, loop তত)
out.append(c1 + c2 + ...)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সময়ের দিক থেকে nested loop-ও **O(k^L · L)**-ই (k = অক্ষর/ digit, L = digit-সংখ্যা) — output-ই তো অত। আসল সমস্যা: **loop-সংখ্যা আগে থেকে জানা নেই**, কারণ digit-string-এর দৈর্ঘ্য variable। তুমি 2টা digit-এর জন্য 2টা loop, 3টার জন্য 3টা — হাতে লেখা অসম্ভব। recursion ঠিক এই "অজানা গভীরতার nested loop"-টাই সুন্দরভাবে সামলায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **এটা একটা variable-depth nested loop**, আর প্রতি level = এক digit-এর অক্ষরের উপর একটা loop। "সব word কী কী?" না ভেবে ভাবো "এই একটা digit-এর জন্য আমার option কী?" — locally কয়েকটা অক্ষর, recursion বাকি digit-গুলোর সব সমন্বয় খুলে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
index `i` ধরে হাঁটো। base case: `i == len(digits)` হলে `path`-কে join করে `out`-এ record করো। নাহলে `digits[i]`-এর প্রতিটা অক্ষরের উপর loop: অক্ষরটা append (choose), `go(i+1)` (explore), pop (un-choose)। প্রথমেই `digits` খালি হলে `[]` return — guard। এটাই k-way Cartesian backtracking, subsets-এর সরাসরি বড় রূপ।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কতগুলো nested loop লাগবে?" নিয়ে আটকে না থেকে ভাবো "প্রতি digit-এ একটা loop, আর গভীরতা recursion সামলাবে।" Subsets-এর 2-way branch-কে শুধু k-way বানিয়ে দাও — কঙ্কাল হুবহু এক, শুধু branch-এর সংখ্যা বদলায়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতি digit-এ k-way branch; leaf-এ পূর্ণ word। `"23"`-এর decision tree:
```text
go(0, "")
a / b | \ c (digit '2' -> a,b,c)
go(1,"a") go(1,"b") go(1,"c")
/ | \ / | \ / | \ (digit '3' -> d,e,f)
d e f d e f d e f
| | | | | | | | |
ad ae af bd be bf cd ce cf
leaf (index == len(digits)) = 3 × 3 = 9টা word।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`letter_combinations("23")`, `go(i, path)`:
1. `go(0,[])`, digit `'2'`→`abc`। choose `a`: `path=['a']`, `go(1,['a'])`।
2. `go(1,['a'])`, digit `'3'`→`def`। choose `d`: record `"ad"`, pop; `e`: record `"ae"`, pop; `f`: record `"af"`, pop।
3. ফিরে pop `a`; choose `b`: একইভাবে `bd, be, bf`।
4. ফিরে pop `b`; choose `c`: `cd, ce, cf`।
5. out = `["ad","ae","af","bd","be","bf","cd","ce","cf"]` — 9টা।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def letter_combinations(digits):
if not digits: # খালি input -> কোনো word নেই
return []
mapping = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
}
out = []
def go(i, path):
if i == len(digits): # base case: সব digit-এ অক্ষর বাছা শেষ
out.append("".join(path))
return
for ch in mapping[digits[i]]:
path.append(ch) # CHOOSE
go(i + 1, path) # EXPLORE
path.pop() # UN-CHOOSE
go(0, [])
return out
# ---- tests (order-independent তুলনা) ----
assert sorted(letter_combinations("23")) == sorted(
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"])
assert sorted(letter_combinations("2")) == ["a", "b", "c"]
assert letter_combinations("") == [] # খালি input
assert sorted(letter_combinations("9")) == ["w", "x", "y", "z"] # 4-অক্ষর
assert len(letter_combinations("234")) == 27 # 3 × 3 × 3
assert len(letter_combinations("79")) == 16 # 4 × 4
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not digits: return []` — খালি string-এ কোনো word নেই; guard আগে।
- `mapping = {...}` — digit → অক্ষর dict, O(1) lookup।
- `if i == len(digits):` — base case: সব digit-এ একটা করে অক্ষর বাছা শেষ।
- `out.append("".join(path))` — `path`-এর অক্ষরগুলো জুড়ে একটা word snapshot record।
- `for ch in mapping[digits[i]]:` — এই digit-এর প্রতিটা অক্ষরে k-way branch।
- `path.append(ch)` / `go(i+1, path)` / `path.pop()` — choose → explore → un-choose।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`letter_combinations("23")`: digit `2`-এর a,b,c-এর প্রতিটার নিচে digit `3`-এর d,e,f বসে — 9টা word (`ad`…`cf`)। order নির্ধারিত হলেও `sorted` দিয়ে তুলনা করায় assert robust। `"2"`→3টা, `""`→`[]`, `"9"`→w,x,y,z (4টা), `"234"`→27, `"79"`→16। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(k^L · L)** — k = প্রতি digit-এর অক্ষর (3 বা 4), L = digit-সংখ্যা; k^L word, প্রতিটা join করতে L।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(L)** — `path` ও call stack-এর গভীরতা L। Output ধরলে **O(k^L · L)**।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- খালি `digits`-এ `[]`-এর বদলে `[""]` ফেরত দেওয়া — base case ভুলভাবে চালু হয়; শুরুতেই guard দাও।
- `path.pop()` ভুলে যাওয়া — পরের branch-এ আগের অক্ষর leak করে।
- record-এ `path` (list) রাখা, `"".join(path)` (string snapshot) না নেওয়া — সব entry একই live list হয়ে যায়।
- mapping-এ digit `0`/`1` ধরে নেওয়া — এদের কোনো অক্ষর নেই; input সাধারণত `2-9`।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Subsets (এই tracker-এর #7)-এর include/exclude branching, এখানে k-way রূপে। [../patterns.md](../patterns.md)-এর Pattern 4-এ এটাকে "digit প্রতি choose, used-set লাগে না" বলা আছে; [../concept.md](../concept.md)-এর `"ab"`-word example দেখো — হুবহু একই কঙ্কাল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Combinations —