Problem link ও উৎস
- **Original source:** Classic backtracking exercise (unique orderings with duplicates)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (choose remaining + duplicate skip)
- **Difficulty:** Medium
- **Pattern:** choose remaining + duplicate skip — sort, তারপর `nums[i]==nums[i-1] and not used[i-1]` হলে skip
- **Basic idea inherited from:** Permutations + sorted skip
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার list `nums` দেওয়া আছে যেখানে **duplicate থাকতে পারে**। তোমার কাজ: এর সব **distinct permutation** বের করা — মানে সব ক্রম, কিন্তু একই ক্রম দুবার নয়। সাধারণ Permutations-এ সব element আলাদা ছিল, তাই `n!`টা ভিন্ন ক্রম; এখানে `[1, 1, 2]`-এর মতো input-এ সরল permutation দুটো সমান 1-কে আলাদা ভেবে নকল ক্রম দেবে। সেই নকলগুলোই বাদ দিতে হবে।
```text
nums = [1, 1, 2]
permutations = [1,1,2], [1,2,1], [2,1,1] (3টা distinct, 3!=6 নয়)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 1, 2] -> Output: [1,1,2], [1,2,1], [2,1,1] (3 distinct)
Input : [1, 2, 3] -> Output: 6টা (সব আলাদা -> 3!)
Edge case 1 (সব সমান): [2, 2, 2] -> Output: [[2,2,2]] (1টা)
Edge case 2 (জোড়া): [1, 1] -> Output: [[1,1]] (1টা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুটো একদম একরকম লাল বল আর একটা নীল বল সারিতে সাজানোর কথা ভাবো। দুই লাল বল দেখতে অভিন্ন, তাই তাদের নিজেদের মধ্যে অদলবদল করলে "নতুন" সাজ হয় না — চোখে একই। তাই গুনতে গেলে দুই লালকে সবসময় একই (বাঁ-থেকে-ডান) ক্রমে বসাও; তাহলে প্রতিটা দৃশ্যমান ভিন্ন সাজ একবারই গোনা হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Permutations + sorted skip**। কঙ্কাল হুবহু Permutations — প্রতি slot-এ unused প্রতিটা item বসাও, `used`-tracker রাখো। নতুন: আগে list **sort** করো (সমান মান পাশাপাশি), তারপর একই slot-এ সমান একটা মান দ্বিতীয়বার বসানোর চেষ্টা করলে — যখন আগের সমান copy এই শাখায় ব্যবহৃত হয়নি — সেটা **skip** করো। sort-and-skip-এর সেই পরিচিত trick, এবার ordering-এর জগতে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো math হলো **duplicate-সহ permutation-সংখ্যা = n! / (m₁!·m₂!·...)**, যেখানে mᵢ হলো প্রতিটা ভিন্ন মানের পুনরাবৃত্তি। সরল permutation সমান copy-গুলোকে আলাদা ধরে ঠিক ওই গুণনীয়কগুণ বেশি ক্রম দেয়। skip-নিয়মটা প্রতিটা distinct ক্রমকে শুধু একটাই canonical পথে গড়তে দেয় — সমান copy-গুলো সবসময় বাঁ-থেকে-ডান ক্রমে ব্যবহৃত হয়, উল্টোভাবে নয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান permutation), একটা **list `out`** (ফলাফল), একটা **boolean array `used`** (কোন index বসানো), আর **call stack**। `nums.sort()` অপরিহার্য — সমান মান পাশাপাশি আনতে, যাতে প্রতিবেশী-ভিত্তিক skip কাজ করে। record-এ `path[:]` snapshot।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`used` array O(1)-তে বলে কোন index ব্যবহৃত — Permutations-এর মতোই seen-set। sort করা list-এ skip-শর্ত শুধু পাশের সমান element (`nums[i-1]`) আর তার `used[i-1]` দেখেই কাজ সারে — আলাদা কোনো জটিল structure লাগে না। `path` mutable বলে choose/un-choose O(1)। দুটো ছোট জিনিস (`used` + sorted neighbor) মিলে duplicate ছাড়াই সব ক্রম দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সাধারণ Permutations চালিয়ে `n!`টা ক্রম গড়ো (সমান copy আলাদা ধরে), তারপর প্রতিটাকে tuple বানিয়ে একটা set-এ ফেলে নকল ঝেড়ে ফেলো।
```text
all = permute(nums) # n!, নকল সহ
unique = set(tuple(p) for p in all)
out = [list(t) for t in unique]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version সবসময় পুরো `n!`টা ক্রম গড়ে — `[2,2,2]`-এ 6টা গড়ে অথচ distinct মাত্র 1টা — তারপর hashing দিয়ে নকল ঝাড়ে। অপচয় দুই দিকে: একই ক্রম বারবার তৈরি, আর প্রতিটা tuple hash করার O(n) খরচ। sorted-skip version নকল শাখায় **ঢোকেই না**, তাই সরাসরি distinct ক্রমগুলোই গড়ে; `[2,2,2]`-এ মাত্র 1টা পথ হাঁটে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **সমান copy-দের মধ্যে কে আগে বসবে তা গুরুত্বহীন** — তাই একটা নিয়ম চাপাই: সমান copy সবসময় বাঁ-থেকে-ডান ক্রমে বসবে। `nums[i] == nums[i-1] and not used[i-1]` ঠিক সেই মুহূর্ত ধরে যখন তুমি একটা সমান copy বসাতে যাচ্ছ অথচ তার ঠিক-আগের সমান copy **এখনো বসেনি** — মানে তুমি ক্রম উল্টে ফেলছ; তাই skip।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`nums.sort()` করো। `go(path)`: `len(path) == len(nums)` হলে record। নাহলে প্রতিটা `i`: `used[i]` হলে skip; `i > 0 and nums[i]==nums[i-1] and not used[i-1]` হলে skip (duplicate); নাহলে `used[i]=True` + append (choose), `go(path)` (explore), pop + `used[i]=False` (un-choose)। মূল Permutations-এ শুধু একটা skip-line যোগ হলো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "নকল কীভাবে ঠেকাব?" — set দিয়ে পরে ঝাড়ার কথা ভেবো না। বরং একটা **canonical নিয়ম** চাপাও: সমান মানগুলো সবসময় তাদের original বাঁ-থেকে-ডান ক্রমে ব্যবহৃত হবে। `not used[i-1]` এই ক্রম-নিয়ম জোর করে — আগের সমানটা না বসিয়ে পরেরটা বসানো মানে ক্রম-ভাঙা, তাই বারণ।
### ছবিতে বোঝা {#7-visual-explanation}
sort করা `[1, 1, 2]`; প্রথম slot-এ দ্বিতীয় 1 skip (আগের সমান copy unused):
```text
go([])
1 / 1 (skip: nums[1]==nums[0], used[0]=False) 2 |
go([1]) go([2])
1/ 2\ 1/ (then 1)
go([1,1]) go([1,2]) go([2,1])->[2,1,1]
2| 1| (used[0] True এখন -> 1 বৈধ)
[1,1,2] [1,2,1]
leaf (len==3) = 3 distinct permutation। প্রথম slot-এর দ্বিতীয় 1 skip বলে নকল নেই।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`permute_unique([1, 1, 2])` (sort করা একই), `go(path)` + `used`:
1. `go([])`: `i=0` (1): `used=[T,F,F]`, `path=[1]`, `go([1])`।
2. `go([1])`: `i=1` (1): আগের সমান copy `used[0]=T` → বৈধ; `path=[1,1]` → `go([1,1])`: `i=2` (2): record `[1,1,2]`; unwind।
3. `go([1])`: `i=2` (2): `path=[1,2]` → `go([1,2])`: `i=1` (1, `used[0]=T`): record `[1,2,1]`; unwind সব।
4. `go([])`: `i=1` (1): `i>0`, `nums[1]==nums[0]`, `used[0]=F` → **skip** (নকল রোধ)।
5. `go([])`: `i=2` (2): `path=[2]` → ভেতরে `[2,1,1]` record।
6. out = `[[1,1,2],[1,2,1],[2,1,1]]` — 3টা distinct।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def permute_unique(nums):
nums.sort() # সমান মান পাশাপাশি
out = []
used = [False] * len(nums)
def go(path):
if len(path) == len(nums): # base case: সব slot ভরা
out.append(path[:]) # snapshot!
return
for i in range(len(nums)):
if used[i]:
continue # ইতিমধ্যে বসানো
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue # আগের সমান copy এখনো বসেনি -> নকল রোধ
used[i] = True # CHOOSE
path.append(nums[i])
go(path) # EXPLORE
path.pop() # UN-CHOOSE
used[i] = False
go([])
return out
# ---- order-independent তুলনার helper (permutation-এ ভেতরের order জরুরি) ----
def norm(list_of_lists):
return sorted(list_of_lists) # শুধু বাইরের list sort, ভেতরের ক্রম অটুট
# ---- tests ----
assert norm(permute_unique([1, 1, 2])) == norm([[1, 1, 2], [1, 2, 1], [2, 1, 1]])
assert len(permute_unique([1, 1, 2])) == 3
assert len(permute_unique([1, 2, 3])) == 6 # সব আলাদা -> 3!
assert permute_unique([2, 2, 2]) == [[2, 2, 2]] # সব সমান -> 1টা
assert permute_unique([1, 1]) == [[1, 1]]
assert len(permute_unique([1, 1, 2, 2])) == 6 # 4!/(2!·2!) = 6
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `nums.sort()` — সমান মান পাশাপাশি, যাতে প্রতিবেশী-skip কাজ করে।
- `if len(path) == len(nums):` — base case: পূর্ণ permutation।
- `if used[i]: continue` — ব্যবহৃত index বাদ (Permutations থেকে)।
- `if i > 0 and nums[i]==nums[i-1] and not used[i-1]: continue` — সমান copy-র ক্রম উল্টে যাওয়া রোধ; এটাই duplicate দমনের চাবি।
- `used[i]=True; path.append(nums[i])` — CHOOSE।
- `go(path)` / `path.pop(); used[i]=False` — EXPLORE তারপর UN-CHOOSE।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`permute_unique([1,1,2])`: প্রথম slot-এ প্রথম 1 দিয়ে শাখা খোলে; দ্বিতীয় 1 (`used[0]=False`) skip হয়, তাই `[1,...]` শুরু একবারই; 2 দিয়ে `[2,1,1]`। ফল 3টা distinct। permutation-এ ভেতরের ক্রম জরুরি, তাই `norm`-এ শুধু **বাইরের** list sort করি (sorted-of-sorted নয়) — assert stable অথচ সঠিকতা যাচাই হয়। `[2,2,2]`-এ 1টা, `[1,1,2,2]`-এ 6টা। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
worst case **O(n · n!)** (সব আলাদা হলে) — distinct permutation যত, প্রতিটার snapshot নিতে n; duplicate থাকলে skip গাছ ছোট করে। sort-এর `O(n log n)` নিচে চাপা।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(n)** — `path`, `used`, call stack n পর্যন্ত। Output ধরলে distinct permutation × n।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- sort না করা — সমান মান ছড়িয়ে, প্রতিবেশী-skip ব্যর্থ, নকল ক্রম বেরোয়।
- skip-শর্তে `not used[i-1]`-এর বদলে `used[i-1]` লেখা — উল্টো দিকে কাটে, বৈধ ক্রম হারায় (অনেকে এই version-ও use করে, কিন্তু তখন যুক্তিটা ভিন্ন; এই note-এ `not used[i-1]` ধরে রাখো)।
- `used` flag reset (`used[i]=False`) ভুলে যাওয়া — পরের branch-এ item আটকে থাকে।
- `out.append(path)` snapshot ছাড়া — সব entry একই live list-এর reference।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Permutations (এই tracker-এর #9)-এর choose-each-remaining + `used`, এখানে sort-and-skip যোগ করে। [../patterns.md](../patterns.md)-এর Pattern 4-এ Permutations II তালিকাভুক্ত; skip-এর ধারণা Pattern 3-এর Subsets II লাইন থেকে — শুধু branching factor "সব unused" হওয়ায় শর্তটা `used[i-1]` জড়িত।
### পরের অনুশীলন {#22-similar-harder-problems}
- Permutations (সব আলাদা) —