Problem link ও উৎস
- **Original source:** Classic backtracking exercise (power set with duplicates)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (include/exclude + duplicate skip)
- **Difficulty:** Medium
- **Pattern:** include/exclude + duplicate skip — sort করে একই level-এ সমান প্রতিবেশী বাদ দাও
- **Basic idea inherited from:** Subsets + sort-and-skip
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার list `nums` দেওয়া আছে যেখানে **duplicate থাকতে পারে**। তোমার কাজ: এর সব **distinct subset** (power set) বের করা — কিন্তু একই subset দুবার নয়। সাধারণ Subsets-এ সব element আলাদা ছিল, তাই কোনো subset repeat হতো না; এখানে `[1, 2, 2]`-এর মতো input-এ সরল include/exclude করলে `[1, 2]` দুবার আসবে (দুটো ভিন্ন 2 থেকে)। সেই duplicate-গুলোই বাদ দিতে হবে।
```text
nums = [1, 2, 2]
subsets = [], [1], [2], [1,2], [2,2], [1,2,2] (মোট 6 distinct)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 2, 2] -> Output: [], [1], [2], [1,2], [2,2], [1,2,2] (6 distinct)
Input : [0] -> Output: [], [0]
Edge case 1 (সব সমান): [1, 1] -> Output: [], [1], [1,1] (3টা)
Edge case 2 (খালি): [] -> Output: [[]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একগুচ্ছ মুদ্রা ভাবো যেখানে দুটো একই রকম 2-টাকা আছে। আলাদা সংগ্রহ বানাতে গেলে "একটা 2-টাকা" সংগ্রহটা দুবার গোনার মানে নেই — দুটো 2-টাকা দেখতে এক, তাই "2-টাকা নিলাম" সিদ্ধান্তটা একবারই গোনো। কোনগুলো নিচ্ছ সেটাই গুরুত্বপূর্ণ, কোন কপিটা নিচ্ছ তা নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Subsets + sort-and-skip**। কঙ্কাল হুবহু Subsets — প্রতিটা item নাও বা বাদ দাও — কিন্তু একটা বাড়তি নিয়ম: আগে list **sort** করো, যাতে সমান সংখ্যাগুলো পাশাপাশি আসে; তারপর কোনো level-এ একই মান দ্বিতীয়বার শুরু করার চেষ্টা করলে সেটা **skip** করো। এই sort-and-skip trick-টাই Combination Sum II-তেও আবার লাগবে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **canonical ordering দিয়ে duplicate দমন**। sort করার পর প্রতিটা distinct subset শুধু একটাই বৈধ পথে তৈরি হয় — প্রথম available copy থেকে। একই value-র দ্বিতীয় copy দিয়ে নতুন একটা subset *শুরু* করলে সেটা আগেই-তৈরি কোনো subset-এর হুবহু নকল হবে, তাই ওই branch কেটে দিই। এতে count `2^n`-এর বদলে distinct subset-সংখ্যায় নেমে আসে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান subset গড়তে), একটা **list `out`** (সব subset জমাতে), আর recursion-এর জন্য **call stack**। প্রথমে `nums.sort()` লাগে যাতে duplicate পাশাপাশি বসে। প্রতিটা node-এই একটা বৈধ subset, তাই record করার সময় `path[:]` snapshot।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
sort করা list-এ সমান মান পাশাপাশি, তাই "এই level-এ এটা কি duplicate?" প্রশ্নের উত্তর শুধু `nums[i] == nums[i-1]` দেখেই O(1)-তে মেলে — আলাদা কোনো seen-set লাগে না, পাশের প্রতিবেশীই যথেষ্ট। `path` mutable বলে append/pop O(1), আর start-index দিয়ে loop চালালে প্রতিটা subset একটাই বাড়ন্ত ক্রমে গড়ে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সাধারণ Subsets চালিয়ে `2^n`টা subset গড়ো, তারপর প্রতিটাকে sort করে একটা set-এ (tuple আকারে) ফেলে duplicate ঝেড়ে ফেলো।
```text
all = subsets(nums) # 2^n, duplicate সহ
unique = set(tuple(sorted(s)) for s in all)
out = [list(t) for t in unique]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version সবসময় পুরো `2^n`টা subset গড়ে, এমনকি অর্ধেক যদি duplicate হয়ও — তারপর hashing দিয়ে ছেঁকে ফেলে। কাজ নষ্ট হয় দুবার: একই subset বারবার তৈরি, আবার dedup-এর জন্য বাড়তি O(n) করে hashing। sort-and-skip version duplicate branch-এ **ঢোকেই না**, তাই সরাসরি distinct subset-গুলোই গড়ে — গড়ার সময়ই pruning, পরে ঝাড়াই নয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **sort করলে duplicate পাশাপাশি**, আর তখন duplicate দমনের নিয়ম একলাইন — "একই level-এ (একই start থেকে) একই মান দ্বিতীয়বার শুরু কোরো না।" `i > start and nums[i] == nums[i-1]` ঠিক এই "একই level-এ দ্বিতীয় copy" অবস্থাটা ধরে। লক্ষ্য করো শর্তটা `i > start`, `i > 0` নয় — গভীরে যাওয়ার সময় সমান copy নেওয়া বৈধ (`[2,2]`), শুধু একই level-এ পাশাপাশি নতুন শুরু বারণ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`nums.sort()` করো। `go(start, path)`: ঢোকার সাথে সাথে `path`-এর snapshot record করো (প্রতিটা node একটা বৈধ subset)। তারপর `i` `start` থেকে শেষ পর্যন্ত: যদি `i > start and nums[i] == nums[i-1]` হয় skip; নাহলে append (choose), `go(i+1, path)` (explore), pop (un-choose)। `i+1` কারণ প্রতিটা item একবারই। এটাই Subsets-এর start-index রূপ + একটা skip-line।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** duplicate ঠেকাতে hashing/set-এর কথা ভেবো না; বরং **sort করে নাও, তারপর একই level-এ সমান প্রতিবেশী এড়িয়ে যাও**। duplicate সমস্যা তখন একটা locality সমস্যায় নেমে আসে — শুধু পাশের element-এর সাথে তুলনা, পুরো ইতিহাস মনে রাখার দরকার নেই।
### ছবিতে বোঝা {#7-visual-explanation}
sort করা `[1, 2, 2]`-এ start-index loop; একই level-এ দ্বিতীয় 2 skip:
```text
go(0, []) -> record []
1 / 2 | 2 (skip: প্রতিবেশী সমান)
go(1,[1]) go(2,[2])
record[1] record[2]
2 | 2 |
go(2,[1,2]) go(3,[2,2])
record[1,2] record[2,2]
2 |
go(3,[1,2,2])
record[1,2,2]
root-এর তৃতীয় branch (দ্বিতীয় 2) skipped -> [2] বা [2,2] duplicate হয় না।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`subsets_with_dup([1, 2, 2])` (sort করা: `[1, 2, 2]`), `go(start, path)`:
1. `go(0,[])`: record `[]`। `i=0` (val 1): append → `go(1,[1])`।
2. `go(1,[1])`: record `[1]`। `i=1` (val 2): append → `go(2,[1,2])`।
3. `go(2,[1,2])`: record `[1,2]`। `i=2` (val 2): append → `go(3,[1,2,2])`: record `[1,2,2]`; pop সব।
4. ফিরে `go(0,[])`: `i=1` (val 2): append → `go(2,[2])`: record `[2]`; `i=2` (val 2): append → record `[2,2]`।
5. `go(0,[])`: `i=2` (val 2) — `i>start(0)` ও `nums[2]==nums[1]` → **skip**।
6. out = `[[],[1],[1,2],[1,2,2],[2],[2,2]]` — 6টা distinct।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def subsets_with_dup(nums):
nums.sort() # duplicate পাশাপাশি আনতে sort
out = []
def go(start, path):
out.append(path[:]) # প্রতিটা node একটা বৈধ subset (snapshot)
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # একই level-এ সমান প্রতিবেশী -> skip
path.append(nums[i]) # CHOOSE
go(i + 1, path) # EXPLORE (i+1: প্রতিটা item একবার)
path.pop() # UN-CHOOSE
go(0, [])
return out
# ---- order-independent তুলনার helper ----
def norm(list_of_lists):
return sorted([sorted(s) for s in list_of_lists])
# ---- tests ----
assert norm(subsets_with_dup([1, 2, 2])) == norm(
[[], [1], [2], [1, 2], [2, 2], [1, 2, 2]])
assert len(subsets_with_dup([1, 2, 2])) == 6
assert norm(subsets_with_dup([0])) == norm([[], [0]])
assert norm(subsets_with_dup([1, 1])) == norm([[], [1], [1, 1]])
assert len(subsets_with_dup([1, 1])) == 3 # duplicate দমন কাজ করছে
assert subsets_with_dup([]) == [[]] # খালি -> শুধু খালি subset
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `nums.sort()` — সমান মান পাশাপাশি, যাতে প্রতিবেশী-তুলনা কাজ করে।
- `out.append(path[:])` — এই node-এর subset-এর snapshot; প্রতি node-ই বৈধ।
- `for i in range(start, len(nums)):` — start থেকে শুরু, যাতে প্রতিটা subset একটাই বাড়ন্ত ক্রমে।
- `if i > start and nums[i] == nums[i-1]: continue` — একই level-এ duplicate value-র দ্বিতীয় copy skip।
- `path.append(nums[i])` / `go(i+1, path)` / `path.pop()` — choose → explore → un-choose; `i+1` মানে item আর reuse হবে না।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`subsets_with_dup([1,2,2])`: প্রতি recursive node-এ একটা subset record হয়; skip-line root-এ দ্বিতীয় 2-এর branch কেটে দেয়, তাই `[2]`/`[2,...]` একবারই আসে। ফল 6টা distinct subset। order নির্ভরযোগ্য নয় (inner order-ও গুরুত্বহীন), তাই `norm`-এ sorted-of-sorted করে তুলনা — তাই assert stable। `[1,1]`-এ 3টা, খালি-তে `[[]]`। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · 2^n)** worst case (সব আলাদা হলে) — distinct subset যত, প্রতিটার snapshot নিতে n; duplicate থাকলে subtree pruning-এ আরও কম। sort-এর `O(n log n)` এর নিচে চাপা পড়ে।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(n)** — `path` ও call stack-এর গভীরতা n। Output ধরলে distinct subset × n।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- sort না করা — duplicate ছড়িয়ে থাকে, প্রতিবেশী-তুলনা ব্যর্থ, repeat subset বেরোয়।
- skip-শর্তে `i > 0` লেখা (`i > start`-এর বদলে) — তখন `[2,2]`-এর মতো বৈধ subset-ও কেটে যায়; গভীরে সমান copy নেওয়া বৈধ, শুধু একই level-এ পাশাপাশি নতুন শুরু বারণ।
- `out.append(path)` snapshot ছাড়া — সব entry একই live list-এর reference।
- `go(i+1)`-এর বদলে `go(i)` — item reuse হয়ে যায় (ওটা Combination Sum-এর নিয়ম, এখানে নয়)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Subsets (এই tracker-এর #7)-এর include/exclude, এখানে sort-and-skip যোগ করে। [../patterns.md](../patterns.md)-এর Pattern 3-এর শেষে বলা আছে "sort করো, তারপর EXCLUDE পাশে সমান প্রতিবেশীদের skip করো" — এই note সেটারই পূর্ণ রূপ। একই skip-trick পরে Combination Sum II (#13)-তে ফিরবে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Combination Sum II (sort-and-skip + target) —