Problem link ও উৎস
- **Original source:** Classic backtracking exercise (all orderings)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (choose each remaining)
- **Difficulty:** Medium
- **Pattern:** choose each remaining — প্রতি slot-এ এখনো unused প্রতিটা item বসিয়ে দেখো (n!)
- **Basic idea inherited from:** Subsets + seen-set (../../05-hashing/)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
আলাদা আলাদা সংখ্যার একটা list `nums` দেওয়া আছে। তোমার কাজ: এর **সব permutation** বের করা — মানে যত রকমভাবে সবগুলো element সাজানো যায়, প্রতিটা ক্রম। Subsets-এ কোন কোন item নেব সেটা ঠিক করতাম; এখানে সব item-ই নিতে হবে, শুধু **কোন order-এ** সেটাই প্রশ্ন। `n`টা element-এর জন্য মোট `n!`টা permutation।
```text
nums = [1, 2, 3]
permutations = [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] (মোট 6 = 3!)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 2, 3] -> Output: [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
Input : [0, 1] -> Output: [0,1], [1,0]
Edge case 1 (একটা): [1] -> Output: [[1]] (একটাই ক্রম)
Edge case 2 (খালি): [] -> Output: [[]] (খালি permutation, মোট 1টা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
তিনজন মানুষকে তিনটা চেয়ারে বসানোর কথা ভাবো। প্রথম চেয়ারে যেকোনো একজন (3 রকম); সে বসে গেলে দ্বিতীয় চেয়ারে বাকি দুজনের একজন (2 রকম); শেষ চেয়ারে যে রইলো সে (1 রকম)। যাকে একবার বসিয়েছ তাকে আর বসানো যাবে না — ঠিক `used` flag। সব রকম বসার বিন্যাসই হলো সব permutation।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Subsets-এর branching, কিন্তু branch factor বদলে গেছে**। Subsets-এ প্রতিটা item-এ ঠিক 2টা branch (নাও/বাদ দাও) ছিল। এখানে প্রতিটা slot-এ branch-এর সংখ্যা = এখনো **ব্যবহার-না-হওয়া item-এর সংখ্যা** (প্রথমে n, তারপর n-1, ...)। তাই একটা **used-tracker** লাগে — সেই [../../05-hashing/](../../05-hashing/README.md)-এর seen-set pattern, যা O(1)-তে বলে কোনটা ইতিমধ্যে বসানো হয়ে গেছে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো math হলো **factorial (n!)**: প্রথম slot-এ n রকম পছন্দ, দ্বিতীয় slot-এ বাকি n-1 রকম, এরপর n-2... তাই মোট `n × (n-1) × ... × 1 = n!` ক্রম। এটা rule of product-এরই রূপ, কিন্তু প্রতিটা ধাপে option একটা করে কমে কারণ ব্যবহৃত item আর নেওয়া যায় না। তাই subsets-এর `2^n`-এর জায়গায় এখানে `n!`।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান permutation গড়তে), একটা **list `out`** (সব permutation জমাতে), একটা **boolean array `used`** (কোন index বসানো হয়ে গেছে track করতে — seen-set), আর recursion-এর জন্য **call stack**। record করার সময় `path[:]` snapshot রাখি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`used` array দিয়ে "এই item কি ইতিমধ্যে বসানো?" প্রশ্নের উত্তর O(1)-তে মেলে — এটাই seen-set-এর কাজ; set না নিয়ে boolean array নিলাম কারণ index দিয়ে দেখি, তাই আরও সস্তা। `path` mutable বলে append/pop O(1), পুরো decision-tree জুড়ে একটাই working permutation reuse করা যায়। আর snapshot না নিলে পরের append/pop আগের record-কেও বদলে দিত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা slot-এ n রকম index ধরে নাও (n^n রকম সমন্বয়); যেগুলোতে প্রতিটা index ঠিক একবার করে আছে শুধু সেগুলো রাখো।
```text
for every tuple of length n over indices 0..n-1:
if tuple uses each index exactly once:
out.append(corresponding values)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version `n^n` রকম সমন্বয় তৈরি করে, কিন্তু এদের মধ্যে মাত্র `n!`টা বৈধ — বাকি সব repeated index-এর জন্য বাতিল। `n = 5`-এ `n^n = 3125` বনাম `n! = 120` — অর্ধেকেরও বেশি কাজ নষ্ট। `used`-tracker দিয়ে আমরা শুরুতেই repeated index-এর branch-এ ঢুকিই না, তাই সরাসরি `n!`টা বৈধ permutation-ই গড়ি, বৃথা কাজ শূন্য।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **permutation গড়া = প্রতিটা slot-এ "এখনো বাকি item-গুলোর একটা" বসানো**। "সব ক্রম কী কী?" না ভেবে ভাবো "এই একটা slot-এ আমার option কী?" — locally option = unused item-গুলো, কিন্তু সব slot মিলে globally সব n! ক্রম বেরিয়ে আসে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`path` ধরে হাঁটো। base case: `len(path) == len(nums)` হলে snapshot record করো। নাহলে প্রতিটা index `i`-র উপর loop: `used[i]` হলে skip; নাহলে `used[i]=True` + `path.append` (choose), `go(path)` (explore), তারপর `path.pop()` + `used[i]=False` (un-choose)। প্রতিটা পূর্ণ শাখা একটা permutation। choose → explore → un-choose-এর নিখুঁত প্রয়োগ, সাথে একটা used-flag।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** দুটো dimension আলাদা করো — **recursion ঠিক করে তুমি কোন SLOT ভরছ**, আর **loop ঠিক করে সেই slot-এ কী যাচ্ছে**। এই দুটো গুলিয়ে ফেললেই permutation কঠিন লাগে; আলাদা ভাবলে এটা subsets-এর মতোই সহজ, শুধু "বাদ দাও" branch-এর জায়গায় "বাকি সবগুলো" branch।
### ছবিতে বোঝা {#7-visual-explanation}
`[1,2,3]`-এর পুরো decision tree: ছয়টি leaf-ই দেখানো। প্রতিটি child থেকে ফেরার পর সেই choice pop করে পরের child নেওয়া হয়।
```mermaid
graph TD
p0["[]"]
p1["[1]"]
p2["[1, 2]"]
p3["[1, 2, 3] · record"]
p2 -->|"choose 3"| p3
p1 -->|"choose 2"| p2
p4["[1, 3]"]
p5["[1, 3, 2] · record"]
p4 -->|"choose 2"| p5
p1 -->|"choose 3"| p4
p0 -->|"choose 1"| p1
p6["[2]"]
p7["[2, 1]"]
p8["[2, 1, 3] · record"]
p7 -->|"choose 3"| p8
p6 -->|"choose 1"| p7
p9["[2, 3]"]
p10["[2, 3, 1] · record"]
p9 -->|"choose 1"| p10
p6 -->|"choose 3"| p9
p0 -->|"choose 2"| p6
p11["[3]"]
p12["[3, 1]"]
p13["[3, 1, 2] · record"]
p12 -->|"choose 2"| p13
p11 -->|"choose 1"| p12
p14["[3, 2]"]
p15["[3, 2, 1] · record"]
p14 -->|"choose 1"| p15
p11 -->|"choose 2"| p14
p0 -->|"choose 3"| p11
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`permute([1, 2])`, `go(path)` + `used`:
1. `go([])`: `i=0` → `used=[T,F]`, `path=[1]`, `go([1])`।
2. `go([1])`: `i=0` used, skip; `i=1` → `used=[T,T]`, `path=[1,2]`, `go([1,2])`: `len==2` → record `[1,2]`; pop → `path=[1]`, `used=[T,F]`।
3. ফিরে `go([])`-তে pop 1 → `path=[]`, `used=[F,F]`; `i=1` → `path=[2]`, `used=[F,T]`।
4. `go([2])`: `i=0` → `path=[2,1]`, record `[2,1]`; pop সব।
5. out = `[[1,2],[2,1]]` — 2টা = 2!।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def permute(nums):
out = []
used = [False] * len(nums)
def go(path):
if len(path) == len(nums): # base case: সব slot ভরা
out.append(path[:]) # snapshot! live path পরে বদলাবে
return
for i in range(len(nums)):
if used[i]: # এই item আগেই বসানো -> skip
continue
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([1, 2, 3])) == norm(
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]])
assert len(permute([1, 2, 3])) == 6 # 3!
assert norm(permute([0, 1])) == norm([[0, 1], [1, 0]])
assert permute([1]) == [[1]] # একটা element
assert permute([]) == [[]] # খালি -> খালি permutation
assert len(permute([1, 2, 3, 4])) == 24 # 4!
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `used = [False] * len(nums)` — কোন index বসানো হয়েছে track করার seen-set।
- `if len(path) == len(nums):` — base case: সব slot ভরে গেছে, একটা পূর্ণ permutation।
- `out.append(path[:])` — `path[:]` snapshot; live `path` পরে বদলাবে।
- `if used[i]: continue` — ইতিমধ্যে বসানো item আবার নয়।
- `used[i] = True; path.append(nums[i])` — CHOOSE: এই item এই slot-এ বসাও।
- `go(path)` — EXPLORE: পরের slot ভরো।
- `path.pop(); used[i] = False` — UN-CHOOSE: undo, যাতে পরের branch পরিষ্কার থাকে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`permute([1,2,3])`: tree-র 6টা পূর্ণ শাখায় 6টা permutation record হয়। order আলাদা আসতে পারে, তাই `norm` দিয়ে বাইরের list sort করে তুলনা করি — কিন্তু ভেতরের ক্রম **নষ্ট করি না** (permutation-এ `[1,2,3]` আর `[3,2,1]` আলাদা), তাই sorted-of-sorted নয়, শুধু outer sort। length 6 (=3!), 4-element-এ 24, একটা element-এ `[[1]]`, খালি-তে `[[]]`। সব মিলে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function permute(nums) {
const out = [];
const used = new Array(nums.length).fill(false);
const go = (path) => {
if (path.length === nums.length) { // base case: সব slot ভরা
out.push([...path]); // snapshot!
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // এই item আগেই বসানো -> skip
used[i] = true; // CHOOSE
path.push(nums[i]);
go(path); // EXPLORE
path.pop(); // UN-CHOOSE
used[i] = false;
}
};
go([]);
return out;
}
// ---- order-independent তুলনা (ভেতরের ক্রম অটুট, শুধু বাইরের list sort) ----
const norm = (lol) => JSON.stringify([...lol].sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));
// ---- test cases ----
assert(norm(permute([1, 2, 3])) === norm([[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]), "main");
assert(permute([1, 2, 3]).length === 6, "3!");
assert(norm(permute([0, 1])) === norm([[0, 1], [1, 0]]), "two");
assert(JSON.stringify(permute([1])) === JSON.stringify([[1]]), "single");
assert(JSON.stringify(permute([])) === JSON.stringify([[]]), "খালি");
assert(permute([1, 2, 3, 4]).length === 24, "4!");
console.log("সব JS test pass!");
```
> **JS টীকা:** এখানে দুটো dimension আলাদা — **recursion ঠিক করে কোন slot ভরছি**, আর **`for` loop ঠিক করে সেই slot-এ কী যাচ্ছে**। `used` boolean array হলো seen-set (Python-এর সমতুল্য), যা O(1)-তে বলে কোন index বসানো হয়ে গেছে। permutation-এ ভেতরের ক্রম জরুরি (`[1,2,3]` ≠ `[3,2,1]`), তাই `norm`-এ শুধু **বাইরের** list sort করি, ভেতরের element sort করি **না**। snapshot `[...path]` আবশ্যক।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function permute(nums: number[]): number[][] {
const out: number[][] = [];
const used: boolean[] = new Array(nums.length).fill(false);
const go = (path: number[]): void => {
if (path.length === nums.length) {
out.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; // CHOOSE
path.push(nums[i]);
go(path); // EXPLORE
path.pop(); // UN-CHOOSE
used[i] = false;
}
};
go([]);
return out;
}
function expect