Problem link ও উৎস
- **Original source:** Classic backtracking exercise (choose k of n)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (start-index combinations)
- **Difficulty:** Medium
- **Pattern:** start-index combinations — fixed size `k`, প্রতিটা combination একটাই বাড়ন্ত ক্রমে
- **Basic idea inherited from:** Fixed size k সহ subsets
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো সংখ্যা `n` আর `k` দেওয়া আছে। তোমার কাজ: `1` থেকে `n` পর্যন্ত সংখ্যাগুলো থেকে ঠিক **`k`টা সংখ্যার সব combination** বের করা। এখানে order গুরুত্বহীন — `[1, 2]` আর `[2, 1]` একই combination, তাই প্রতিটাকে একবারই গোনা হয় (সাধারণত বাড়ন্ত ক্রমে লেখা)। Subsets-এ সব মাপের subset লাগত; এখানে শুধু **মাপ ঠিক `k`** এমনগুলো।
```text
n = 4, k = 2
combinations = [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] (মোট 6 = C(4,2))
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=4, k=2 -> Output: [1,2],[1,3],[1,4],[2,3],[2,4],[3,4] (6টা)
Input : n=3, k=3 -> Output: [1,2,3] (1টা)
Edge case 1 (k=1): n=4, k=1 -> Output: [1],[2],[3],[4] (4টা)
Edge case 2 (k=n): n=1, k=1 -> Output: [1] (1টা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা দলের 4 জন বন্ধু থেকে 2 জনের কমিটি বানানোর কথা ভাবো। "রাহুল আর মীরা" আর "মীরা আর রাহুল" একই কমিটি — তাই গণনায় একবারই ধরো। সবসময় তালিকার আগের নাম আগে লিখলে (বাড়ন্ত ক্রম) প্রতিটা জোড়া স্বাভাবিকভাবেই একবার করে আসে; সেটাই start-index-এর কাজ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Subsets, কিন্তু মাপ fixed `k`**। Subsets সব মাপের সংগ্রহ দিত (`2^n`); এখানে শুধু ঠিক `k`-মাপের চাই। তাই দুটো ছোট পরিবর্তন: (1) base case এখন `len(path) == k` (সব index পেরোনো নয়), আর (2) order গুরুত্বহীন বলে একটা **start index** চাপাই — যাতে প্রতিটা combination কেবল বাড়ন্ত ক্রমে একবারই তৈরি হয়, `[2,1]`-এর মতো নকল আসে না।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো math হলো **binomial coefficient `C(n, k) = n! / (k!·(n-k)!)`** — n থেকে k বেছে নেওয়ার রকম-সংখ্যা, যেখানে order গোনা হয় না। start index দিয়ে আমরা প্রতিটা subset-কে তার বাড়ন্ত-ক্রম প্রতিনিধি দিয়ে গড়ি, ফলে permutation-এর k! গুণ অতিরিক্ত গণনা স্বয়ংক্রিয়ভাবে বাদ পড়ে — গাছের গঠনই duplicate দমন করে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান combination গড়তে), একটা **list `out`** (সব combination জমাতে), একটা **integer `start`** (পরবর্তী পছন্দ কোথা থেকে শুরু), আর recursion-এর জন্য **call stack**। record করার সময় `path[:]` snapshot।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`start` integer-টাই এখানে আসল নায়ক: এটা নিশ্চিত করে আমরা কখনো পিছনের সংখ্যায় ফিরি না, তাই প্রতিটা combination শুধু বাড়ন্ত ক্রমে গড়ে — duplicate ঠেকাতে কোনো set বা skip-line লাগে না, শুধু একটা integer। `path` mutable বলে append/pop O(1), পুরো গাছ জুড়ে একটাই working combination reuse হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: Subsets চালিয়ে `1..n`-এর সব `2^n`টা subset গড়ো, তারপর শুধু যেগুলোর দৈর্ঘ্য ঠিক `k` সেগুলো রাখো।
```text
out = [s for s in subsets(range(1, n+1)) if len(s) == k]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version সবসময় পুরো `2^n`টা subset গড়ে, অথচ আমরা চাই মাত্র `C(n, k)`টা। বেশিরভাগ মাপ ভুল হওয়ায় ছুঁড়ে ফেলা হয় — যেমন `n=20, k=2`-এ `2^20 ≈ 10` লক্ষ গড়ে মাত্র 190টা রাখা হয়। start-index version base case-এ `len == k` দেখে থেমে যায় আর `k`টা item পূর্ণ হলেই গভীরে আর নামে না, তাই সরাসরি `C(n,k)`টাই গড়ে — বাকি branch-এ ঢোকেই না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **order গুরুত্বহীন combination = বাড়ন্ত-ক্রমের subset**। `[2,1]`-কে `[1,2]`-এর নকল হিসেবে আলাদা করে ঠেকানোর দরকার নেই — শুধু সবসময় বড় index-এর দিকে এগোও (`start`)। আর "k-মাপ" condition base case-এ বসিয়ে দিলে গাছটা গভীরে `k` level-এর বেশি যায় না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`go(start, path)`: base case `len(path) == k` হলে snapshot record। নাহলে `i` `start` থেকে `n` পর্যন্ত: append (choose), `go(i+1, path)` (explore), pop (un-choose)। `i+1` মানে প্রতিটা সংখ্যা একবার আর সবসময় বাড়ন্ত ক্রম। চাইলে pruning: যদি বাকি সংখ্যা (`n - i + 1`) থেকে প্রয়োজনীয় বাকি (`k - len(path)`) পূরণ না হয়, loop আগেই থামাও — `for i in range(start, n - (k - len(path)) + 2)`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "n থেকে k বাছার সব রকম" বিশাল ভেবো না; ভাবো "এখন একটা সংখ্যা নিচ্ছি, পরেরটা অবশ্যই এর চেয়ে বড় হবে।" এই "সবসময় সামনে এগোও" নিয়মটাই order-গুরুত্বহীনতা সামলায় — duplicate-এর চিন্তা পুরো উবে যায়, শুধু `start` বাড়াও।
### ছবিতে বোঝা {#7-visual-explanation}
start-index loop, base case `len == k`। `n = 4, k = 2`-এর decision tree:
```text
go(1, [])
1 / 2 | 3 | \ 4 (k বাকি নেই -> ফলহীন)
go(2,[1]) go(3,[2]) go(4,[3])
2/ 3| 4\ 3| 4\ 4|
[1,2][1,3][1,4] [2,3][2,4] [3,4]
leaf (len(path) == k = 2) = 6 = C(4,2) combination।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`combine(4, 2)`, `go(start, path)`:
1. `go(1,[])`: `i=1`: append → `go(2,[1])`।
2. `go(2,[1])`: `len<2`। `i=2`: record `[1,2]`; `i=3`: `[1,3]`; `i=4`: `[1,4]`; pop 1।
3. `go(1,[])`: `i=2`: append → `go(3,[2])`: `i=3`: `[2,3]`; `i=4`: `[2,4]`; pop।
4. `go(1,[])`: `i=3`: append → `go(4,[3])`: `i=4`: `[3,4]`; pop।
5. `go(1,[])`: `i=4`: append → `go(5,[4])`: `i` range খালি, কোনো leaf নয়।
6. out = `[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]` — 6টা।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def combine(n, k):
out = []
def go(start, path):
if len(path) == k: # base case: k-মাপ পূর্ণ
out.append(path[:]) # snapshot!
return
for i in range(start, n + 1): # start থেকে: সবসময় বাড়ন্ত ক্রম
path.append(i) # CHOOSE
go(i + 1, path) # EXPLORE (i+1: পরেরটা বড় হবে)
path.pop() # UN-CHOOSE
go(1, [])
return out
# ---- order-independent তুলনার helper ----
def norm(list_of_lists):
return sorted([sorted(s) for s in list_of_lists])
# ---- tests ----
assert norm(combine(4, 2)) == norm(
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
assert len(combine(4, 2)) == 6 # C(4,2)
assert combine(3, 3) == [[1, 2, 3]] # k = n -> একটাই
assert norm(combine(4, 1)) == norm([[1], [2], [3], [4]])
assert combine(1, 1) == [[1]]
assert len(combine(5, 3)) == 10 # C(5,3)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if len(path) == k:` — base case: ঠিক `k`টা সংখ্যা জমে গেছে, একটা পূর্ণ combination।
- `out.append(path[:])` — snapshot; live `path` পরে বদলাবে।
- `for i in range(start, n + 1):` — `start` থেকে শুরু বলে আর কখনো পিছনে ফিরি না — বাড়ন্ত ক্রম নিশ্চিত।
- `path.append(i)` — CHOOSE: এই সংখ্যা নিলাম।
- `go(i + 1, path)` — EXPLORE: পরের পছন্দ `i+1` থেকে, তাই পরেরটা সবসময় বড়।
- `path.pop()` — UN-CHOOSE: undo, যাতে পরের `i` পরিষ্কারভাবে try হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`combine(4,2)`: প্রতিটা leaf-এ (`len==2`) একটা combination record হয়; start-index বড়-index-এর দিকে এগোয় বলে `[2,1]`-এর মতো নকল কখনো তৈরি হয় না। ফল 6টা (=C(4,2))। order গুরুত্বহীন, তাই `norm`-এ sorted-of-sorted করে তুলনা — assert stable। `k=n`-এ একটাই, `k=1`-এ n-টা, `C(5,3)=10`। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(k · C(n, k))** — `C(n, k)`টা combination, প্রতিটার snapshot নিতে k পর্যন্ত copy। pruning থাকলে গাছ আরও ছোট।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(k)** — `path` ও call stack-এর গভীরতা k পর্যন্ত। Output ধরলে **O(k · C(n, k))**।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `start` ব্যবহার না করে প্রতিবার `1..n` loop — তখন `[1,2]` আর `[2,1]` দুটোই আসে (combination নয়, permutation)।
- `go(i+1)`-এর বদলে `go(start)` বা `go(i)` — হয় duplicate, নয় reuse; combination-এ প্রতিটা একবার ও সামনে এগোনো চাই।
- base case `len(path) == k`-এর বদলে `start > n` দেওয়া — তখন সব মাপের subset বেরোয়, fixed-k নয়।
- `out.append(path)` snapshot ছাড়া — সব entry একই live list-এর reference।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Subsets (এই tracker-এর #7), এখানে fixed size `k` + start-index। [../patterns.md](../patterns.md)-এর Pattern 5 (Combinations with pruning)-এ start-index-এর ভূমিকা ব্যাখ্যা করা — "প্রতিটা combination একটাই canonical order-এ তৈরি"। এই start-index কঙ্কালই পরের Combination Sum (#12) আর Combination Sum II (#13)-এর ভিত্তি।
### পরের অনুশীলন {#22-similar-harder-problems}
- Combination Sum (start-index + reuse + target) —