Problem link ও উৎস
- **Original source:** Classic backtracking exercise (target sum, each used once, with duplicates)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (pruning + duplicate handling)
- **Difficulty:** Medium
- **Pattern:** pruning + duplicate handling — sort, target-prune (break), একই level-এ সমান প্রতিবেশী skip
- **Basic idea inherited from:** Combination Sum + Subsets II-র skip trick
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
সংখ্যার একটা list `candidates` (যেখানে **duplicate থাকতে পারে**) আর একটা `target` দেওয়া আছে। তোমার কাজ: এমন সব **distinct সংগ্রহ** বের করা যাদের যোগফল ঠিক `target` — কিন্তু এবার প্রতিটা সংখ্যা (তার position ধরে) **একবারই ব্যবহার করা যাবে**, আর একই সংগ্রহ দুবার নয়। Combination Sum-এ reuse চলত আর সব আলাদা ছিল; এখানে reuse বন্ধ, আর input-এর duplicate থেকে যেন duplicate সংগ্রহ না আসে।
```text
candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
combinations = [1,1,6], [1,2,5], [1,7], [2,6] (প্রতিটা একবার, প্রতিটা সংখ্যা নিজ position-এ একবার)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [10,1,2,7,6,1,5], target=8 -> Output: [1,1,6],[1,2,5],[1,7],[2,6]
Input : [2,5,2,1,2], target=5 -> Output: [1,2,2],[5]
Edge case 1 (অসম্ভব): [2,4], target=3 -> Output: []
Edge case 2 (একটাই মেলে): [1], target=1 -> Output: [[1]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
হাতের কিছু নির্দিষ্ট নোট (যার মধ্যে দুটো একই মানের নোট আছে) দিয়ে ঠিক একটা বিল মেটানোর কথা ভাবো — প্রতিটা নোট একবারই দেওয়া যায় (reuse নেই)। দুটো একই 1-টাকার নোট থাকলে "একটা 1 দিলাম" সিদ্ধান্তটা একই level-এ দুবার গোনার মানে নেই (একই ফল); কিন্তু একটা সংগ্রহে দুটো 1 দুটোই ব্যবহার করা বৈধ। এই সূক্ষ্ম পার্থক্যই `i > start` skip সামলায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি দুটোর সংকর: **Combination Sum + Subsets II-র skip trick**। Combination Sum থেকে নিই start-index, running `remaining`, আর sorted target-prune (`break`)। Subsets II থেকে নিই sort-and-skip — একই recursion level-এ সমান প্রতিবেশী বাদ দেওয়া। আর reuse বন্ধ করতে recurse করি `go(i+1, ...)` দিয়ে (Combination Sum-এ ছিল `go(i)`)। দুই idea মিলেই এই problem।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুটো আলাদা duplicate-উৎস সামলানো। (a) **একই সংগ্রহ ভিন্ন order-এ** — start-index দিয়ে বাড়ন্ত ক্রম চাপিয়ে দমন (Combinations থেকে)। (b) **input-এ সমান মান একাধিক copy** — sort করে একই level-এ দ্বিতীয় copy skip করে দমন (Subsets II থেকে)। দুটো ভিন্ন duplicate, দুটো ভিন্ন অস্ত্র — গুলিয়ে ফেললেই হয় নকল আসে নয় বৈধ সংগ্রহ হারায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান সংগ্রহ), একটা **list `out`** (ফলাফল), একটা **integer `remaining`** (running complement), আর **call stack**। `candidates.sort()` অপরিহার্য — duplicate পাশাপাশি আনতে আর target-prune-এর `break` বৈধ করতে। record-এ `path[:]` snapshot।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
একটাই sort দুটো কাজ সারে: সমান মান পাশাপাশি (skip-line-এর প্রতিবেশী-তুলনা কাজ করে) আর বাড়ন্ত ক্রম (target ছাড়ালে `break` বৈধ)। `remaining` integer base case (`==0`) ও prune (`> remaining`) দুটোই O(1)-তে দেয়। `path` mutable বলে choose/un-choose O(1)। আলাদা seen-set লাগে না — পাশের প্রতিবেশীই duplicate বলে দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা position একবার-নাও/বাদ-দাও করে সব `2^n`টা subset গড়ো (position-ভিত্তিক, তাই দুটো সমান copy আলাদা গোনা হবে); যেগুলোর যোগফল `target` সেগুলো রাখো; তারপর sort করে set-এ ফেলে duplicate সংগ্রহ ঝেড়ে ফেলো।
```text
all = subsets_by_position(candidates) # 2^n
hits = [s for s in all if sum(s) == target]
out = dedup(sorted(s) for s in hits) # নকল সংগ্রহ ঝাড়
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই version সবসময় পুরো `2^n` subset গড়ে — target ছাড়িয়ে যাওয়া শাখাতেও গভীরে নামে — তারপর target-filter আর dedup-এ আরও কাজ। দুই অপচয়: hopeless শাখায় সময়, আর duplicate সংগ্রহ বারবার গড়ে পরে ঝাড়া। sort + target-prune (`break`) hopeless লেজ গাছেই কাটে, আর `i > start` skip duplicate সংগ্রহ **গড়ার আগেই** আটকায় — পরে ঝাড়ার দরকারই পড়ে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **দুটো ভিন্ন duplicate, দুটো ভিন্ন সমাধান** — (a) order-জনিত নকল start-index সামলায়, (b) সমান-মান-জনিত নকল `i > start and candidates[i]==candidates[i-1]` skip সামলায়। আর reuse বন্ধ করতে `go(i+1)`। তিনটা ছোট নিয়ম একসাথে: start-index, skip-line, আর `i+1` — এদের একটাও ভুললে হয় নকল নয় হারানো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`candidates.sort()` করো। `go(start, path, remaining)`: `remaining == 0` হলে record। নাহলে `i` `start` থেকে: যদি `i > start and candidates[i]==candidates[i-1]` → `continue` (duplicate skip); যদি `candidates[i] > remaining` → `break` (target-prune)। নাহলে append (choose), `go(i+1, path, remaining - candidates[i])` (explore — `i+1`, each used once), pop (un-choose)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** Combination Sum-এর কঙ্কালে ঠিক **দুটো লাইন বদলাও** — `go(i)` কে `go(i+1)` করো (reuse বন্ধ), আর loop-এর শুরুতে Subsets II-র skip-line বসাও (`i > start` সমান প্রতিবেশী)। নতুন কিছু আবিষ্কার নয়, দুটো আগের note-এর অংশ জোড়া লাগানো — এটাই inheritance-এর সৌন্দর্য।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট পূর্ণ উদাহরণ: sorted input `[1,1,2]`, target 3। প্রতিটি index সর্বোচ্চ একবার নেওয়া যায়।
```mermaid
graph TD
R["[]; left=3"] -->|"index 0: 1"| A["[1]; left=2"]
R -->|"index 1: 1"| SK["same level duplicate: skip"]
R -->|"index 2: 2"| B["[2]; left=1; no items left"]
A -->|"index 1: 1"| C["[1,1]; left=1; next 2 is too large"]
A -->|"index 2: 2"| D["[1,2]; left=0; record"]
```
ফল `[[1,2]]`। Root-এ দ্বিতীয় 1 বাদ, কিন্তু `[1]`-এর পরে পরের 1 নেওয়া যায়: `i > start` শর্ত একই level-এর duplicate-ই আটকায়। বড় input `[1,1,2,5,6,7,10]`, target 8-এর ফল `[[1,1,6],[1,2,5],[1,7],[2,6]]`।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`combination_sum2([10,1,2,7,6,1,5], 8)` (sort: `[1,1,2,5,6,7,10]`):
1. `go(0,[],8)`: `i=0` (1): append → `go(1,[1],7)`।
2. `go(1,[1],7)`: `i=1` (1): append → `go(2,[1,1],6)`: `i=4` (6): record `[1,1,6]`...; pop চেইন।
3. `go(1,[1],7)`: `i=2` (2): → `go(3,[1,2],5)`: `i=3` (5): record `[1,2,5]`।
4. `go(1,[1],7)`: `i=5` (7): record `[1,7]`।
5. ফিরে `go(0,[],8)`: `i=1` (1) — `i>start(0)` ও সমান → **skip**। `i=2` (2): → `go(3,[2],6)`: `i=4` (6): record `[2,6]`।
6. out = `[[1,1,6],[1,2,5],[1,7],[2,6]]` — 4টা distinct।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def combination_sum2(candidates, target):
candidates.sort() # duplicate পাশাপাশি + prune-এ break বৈধ
out = []
def go(start, path, remaining):
if remaining == 0: # base case: যোগফল ঠিক target
out.append(path[:]) # snapshot!
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue # একই level-এ সমান প্রতিবেশী -> skip
if candidates[i] > remaining:
break # PRUNE: পরের সবগুলোও বড় (sorted)
path.append(candidates[i]) # CHOOSE
go(i + 1, path, remaining - candidates[i]) # EXPLORE (i+1: each once)
path.pop() # UN-CHOOSE
go(0, [], target)
return out
# ---- order-independent তুলনার helper ----
def norm(list_of_lists):
return sorted([sorted(s) for s in list_of_lists])
# ---- tests ----
assert norm(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8)) == norm(
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]])
assert norm(combination_sum2([2, 5, 2, 1, 2], 5)) == norm([[1, 2, 2], [5]])
assert combination_sum2([2, 4], 3) == [] # অসম্ভব
assert combination_sum2([1], 1) == [[1]]
assert len(combination_sum2([1, 1, 1, 1], 2)) == 1 # শুধু [1,1], নকল নয়
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `candidates.sort()` — সমান মান পাশাপাশি (skip-এর জন্য) ও বাড়ন্ত ক্রম (break-এর জন্য)।
- `if remaining == 0:` — base case: যোগফল target।
- `if i > start and candidates[i] == candidates[i-1]: continue` — একই level-এ duplicate value-র দ্বিতীয় copy skip (Subsets II trick)।
- `if candidates[i] > remaining: break` — target-prune: পরেরগুলোও বড়, লেজ কাটো।
- `go(i + 1, path, remaining - candidates[i])` — EXPLORE: `i+1` মানে প্রতিটা position একবার (reuse নেই)।
- `path.append/pop` — choose → un-choose।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`combination_sum2([10,1,2,7,6,1,5],8)`: sort-এর পর `[1,1,2,5,6,7,10]`; প্রথম 1-শাখা `[1,1,6]/[1,2,5]/[1,7]` দেয়, root-এর দ্বিতীয় 1 skip হয় (নাহলে `[1,7]` দুবার আসত), 2-শাখা `[2,6]` দেয়। ফল 4টা distinct। order ও inner order গুরুত্বহীন, তাই `norm`-এ sorted-of-sorted তুলনা — assert stable। অসম্ভব target-এ `[]`, `[1,1,1,1]/2`-এ একটাই `[1,1]`। সব মিলে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
worst case **O(2^n · n)** — n position-এ নাও/বাদ-দাও, প্রতিটা বৈধ সংগ্রহের snapshot নিতে n; বাস্তবে target-prune + duplicate-skip গাছ অনেক ছোট করে। sort-এর `O(n log n)` নিচে চাপা।
### অতিরিক্ত জায়গা {#19-space-complexity}
Output বাদ দিলে **O(n)** — call stack + `path` n পর্যন্ত গভীর। Output ধরলে সব সংগ্রহের মোট আকার।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `go(i+1)`-এর বদলে `go(i)` — reuse খুলে যায়, একই position বারবার (এটা Combination Sum, এই problem নয়)।
- skip-line বাদ দেওয়া — input duplicate থেকে নকল সংগ্রহ আসে।
- skip-শর্তে `i > 0` (`i > start`-এর বদলে) — গভীরে বৈধ `[1,1,...]`-ও কেটে যায়, বৈধ সংগ্রহ হারায়।
- sort না করা — না prune-এর `break` বৈধ, না skip-এর প্রতিবেশী-তুলনা কাজ করে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Combination Sum (#12)-এর start-index + remaining + target-prune, আর Subsets II (#10)-এর sort-and-skip। [../patterns.md](../patterns.md)-এর Pattern 5-এ এটা তালিকাভুক্ত; skip-trick-এর শিকড় Pattern 3-এর শেষ লাইনে। দুই আগের note ভালো বুঝলে এই problem শুধু তাদের জোড়া।
### পরের অনুশীলন {#22-similar-harder-problems}
- Combination Sum (reuse allowed, সব আলাদা) —