Problem link ও উৎস
- **Original source:** Classic backtracking exercise (combinations summing to target)
- **Platform:** LeetCode —
- **Topic:** recursion / backtracking (combinations with pruning)
- **Difficulty:** Medium
- **Pattern:** combinations with pruning — start-index + reuse, sorted হলে target ছাড়ালে break
- **Basic idea inherited from:** Combinations + remaining-target complement
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
আলাদা ধনাত্মক সংখ্যার একটা list `candidates` আর একটা `target` দেওয়া আছে। তোমার কাজ: এমন সব সংগ্রহ বের করা যাদের যোগফল ঠিক `target` — আর প্রতিটা সংখ্যা **যতবার খুশি ব্যবহার করা যায়** (reuse allowed)। order গুরুত্বহীন, তাই `[2, 3]` আর `[3, 2]` একই, একবার গোনা। Combinations-এ মাপ fixed ছিল; এখানে মাপ যাই হোক, **যোগফল = target** এই শর্তটাই আসল।
```text
candidates = [2, 3, 6, 7], target = 7
combinations = [2, 2, 3], [7] (2+2+3 = 7, এবং 7 = 7)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [2,3,6,7], target=7 -> Output: [2,2,3], [7]
Input : [2,3,5], target=8 -> Output: [2,2,2,2], [2,3,3], [3,5]
Edge case 1 (অসম্ভব): [2], target=1 -> Output: [] (1 বানানো যায় না)
Edge case 2 (একই বারবার): [1], target=2 -> Output: [[1,1]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
খুচরো পয়সা দিয়ে ঠিক একটা দাম মেটানোর কথা ভাবো, যেখানে প্রতিটা মানের পয়সা অসীম সংখ্যায় আছে (reuse)। তুমি একটা পয়সা দিলে বাকি দেনা কমে; সেই কম দেনাটা একই সমস্যা, ছোট হয়ে। আর হাতের সবচেয়ে ছোট পয়সাও যদি বাকি দেনার চেয়ে বড় হয়, তখন আর কিছু দিয়েই হবে না — থেমে যাও (prune)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **Combinations + remaining-target complement**। Combinations-এর মতোই একটা **start index** দিয়ে বাড়ন্ত ক্রমে এগোই (duplicate সংগ্রহ ঠেকাতে)। নতুন দুটো জিনিস: (1) base case এখন `remaining == 0` (মাপ নয়, যোগফল), আর (2) reuse allowed বলে recurse করি `go(i, ...)` দিয়ে — `i+1` নয়, যাতে একই সংখ্যা আবার নেওয়া যায়। "remaining target" হলো সেই complement যেটা [../../05-hashing/](../../05-hashing/README.md)-এর complement-thinking থেকে আসে — এখনো কতটা যোগফল দরকার।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **target-কে subtraction দিয়ে ছোট করা**: একটা সংখ্যা `c` নিলে সমস্যাটা হয়ে যায় "`remaining - c` যোগফল কীভাবে বানাব?" — একই সমস্যা, ছোট target-এ। sort করা থাকলে একটা শক্তিশালী pruning খোলে: কোনো candidate `remaining`-এর চেয়ে বড় হলে, তার পরের সবগুলোও বড় (sorted), তাই পুরো লেজটা `break` দিয়ে কেটে ফেলা যায় — একটা একটা করে skip নয়, এক কোপে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **list `path`** (বর্তমান সংগ্রহ গড়তে), একটা **list `out`** (সব সংগ্রহ জমাতে), একটা **integer `remaining`** (এখনো কত যোগফল বাকি — running complement), আর recursion-এর জন্য **call stack**। sort করার জন্য candidate list-টা আগে sort করি যাতে pruning খাটে। record-এ `path[:]` snapshot।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`remaining` integer-টা প্রতি level-এ "আর কত দরকার" বলে দেয় — base case (`==0`) আর prune (`candidate > remaining`) দুটোই এই একটা সংখ্যা দেখেই হয়, পুরো `path` যোগ করে দেখার দরকার নেই। sorted list-এ `>` test-এর পর `break` বৈধ কারণ পরেরগুলো নিশ্চিত আরও বড়। `path` mutable বলে append/pop O(1)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: যেহেতু reuse চলে আর target সীমিত, প্রতিটা candidate-এর জন্য 0..(target/c) বার নেওয়ার সব সমন্বয় চেষ্টা করো; প্রতিটার যোগফল দেখো।
```text
for count of candidate[0] in 0..target//c0:
for count of candidate[1] in 0..remaining//c1:
... (candidate যত, nested loop তত)
if total == target: record
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই nested-count version-এ loop-সংখ্যা candidate-সংখ্যার সমান, আর প্রতিটা loop target পর্যন্ত যেতে পারে — অনেক সমন্বয় target ছাড়িয়ে গিয়েও তৈরি হয়, তারপর বাতিল হয়। আসল অপচয়: target পেরিয়ে যাওয়ার অনেক পরেও গণনা চলতে থাকে। recursion + sorted-break ঠিক যে মুহূর্তে candidate `remaining` ছাড়ায় সেই মুহূর্তেই পুরো subtree কেটে দেয়, তাই কখনো target ছাড়ানো শাখায় গভীরে নামে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা সংখ্যা নেওয়া = target থেকে সেটা বিয়োগ করে একই সমস্যা ছোট করা**, আর reuse মানে নেওয়ার পরেও **একই index থেকে** আবার শুরু করা যায়। দ্বিতীয় observation: sort করা থাকলে `candidate > remaining` হওয়া মাত্র লুপ `break` — কারণ পরের সবগুলো আরও বড়, তারাও fail করবে। এই prune-ই brute force আর backtracking-এর গতির পার্থক্য।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`candidates.sort()` করো। `go(start, path, remaining)`: `remaining == 0` হলে snapshot record। নাহলে `i` `start` থেকে: যদি `candidates[i] > remaining` হয় `break` (sorted prune)। নাহলে append (choose), `go(i, path, remaining - candidates[i])` (explore — `i`, কারণ reuse allowed), pop (un-choose)। `start` duplicate সংগ্রহ ঠেকায়, `i` (i+1 নয়) reuse খোলে, `break` hopeless লেজ কাটে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন কোন সংখ্যার সংগ্রহ target দেয়?" — পুরোটা একসাথে না ভেবে ভাবো "একটা সংখ্যা নিলে বাকি target কত, আর সেই ছোট target কীভাবে বানাব?" target-টাকেই recursion-এর সঙ্কুচিত-হতে-থাকা state বানাও। আর reuse মানে শুধু একটাই বদল: পরের call-এ `i+1` নয়, `i` — একই সংখ্যায় থেকে যাওয়ার অনুমতি।
### ছবিতে বোঝা {#7-visual-explanation}
`candidates=[2,3,6,7]`, target 7। সব বৈধ recursive call এখানে আছে। `candidate > remaining` হলে sorted হওয়ায় সেটি এবং তার পরের বড় candidate-গুলো বাদ যায়।
```mermaid
graph TD
c0["[]; left=7; search"]
c1["[2]; left=5; search"]
c2["[2, 2]; left=3; search"]
c3["[2, 2, 2]; left=1; dead end"]
c2 -->|"2"| c3
c4["[2, 2, 3]; left=0; record"]
c2 -->|"3"| c4
c1 -->|"2"| c2
c5["[2, 3]; left=2; dead end"]
c1 -->|"3"| c5
c0 -->|"2"| c1
c6["[3]; left=4; search"]
c7["[3, 3]; left=1; dead end"]
c6 -->|"3"| c7
c0 -->|"3"| c6
c8["[6]; left=1; dead end"]
c0 -->|"6"| c8
c9["[7]; left=0; record"]
c0 -->|"7"| c9
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`combination_sum([2, 3, 6, 7], 7)` (sort করা একই), `go(start, path, remaining)`:
1. `go(0,[],7)`: `i=0` (2): append → `go(0,[2],5)`।
2. `go(0,[2],5)`: `i=0` (2): → `go(0,[2,2],3)`।
3. `go(0,[2,2],3)`: `i=0` (2): → `go(0,[2,2,2],1)`: `i=0` (2>1) → `break`, dead; pop।
4. `go(0,[2,2],3)`: `i=1` (3, =remaining): → `go(1,[2,2,3],0)`: record `[2,2,3]`; pop।
5. unwind করে root-এর `i=3` (7, =remaining): → `go(3,[7],0)`: record `[7]`।
6. out = `[[2,2,3],[7]]` — 2টা।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def combination_sum(candidates, target):
candidates.sort() # sorted: 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 candidates[i] > remaining:
break # PRUNE: পরের সবগুলোও বড় (sorted)
path.append(candidates[i]) # CHOOSE
go(i, path, remaining - candidates[i]) # EXPLORE (i: reuse allowed)
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_sum([2, 3, 6, 7], 7)) == norm([[2, 2, 3], [7]])
assert norm(combination_sum([2, 3, 5], 8)) == norm(
[[2, 2, 2, 2], [2, 3, 3], [3, 5]])
assert combination_sum([2], 1) == [] # 1 বানানো অসম্ভব
assert combination_sum([1], 2) == [[1, 1]] # reuse: 1+1
assert len(combination_sum([2, 3, 6, 7], 7)) == 2
assert combination_sum([8], 7) == [] # candidate > target
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `candidates.sort()` — sorted হলে `break`-prune বৈধ হয়।
- `if remaining == 0:` — base case: যোগফল ঠিক target হয়ে গেছে।
- `out.append(path[:])` — snapshot; live `path` পরে বদলাবে।
- `for i in range(start, ...)` — `start` থেকে বলে duplicate সংগ্রহ আসে না।
- `if candidates[i] > remaining: break` — PRUNE: এটা বড় হলে পরেরগুলোও বড়, পুরো লেজ কাটো।
- `go(i, path, remaining - candidates[i])` — EXPLORE: `i` (i+1 নয়) মানে একই সংখ্যা আবার নেওয়া যায় (reuse)।
- `path.pop()` — UN-CHOOSE: undo।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`combination_sum([2,3,6,7],7)`: 2-এর শাখা গভীরে গিয়ে `[2,2,3]` (যোগ 7) record করে; `[2,2,2]`-এ remaining 1, সবচেয়ে ছোট 2-ও বড় → `break`, dead end; root-এর 7-শাখা `[7]` দেয়; 6 কখনো কাজে লাগে না। ফল 2টা সংগ্রহ। order গুরুত্বহীন, তাই `norm`-এ sorted-of-sorted তুলনা — assert stable। অসম্ভব target-এ `[]`, reuse-এ `[1,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 combinationSum(candidates, target) {
candidates.sort((a, b) => a - b); // sorted: prune-এ break বৈধ হয়
const out = [];
const go = (start, path, remaining) => {
if (remaining === 0) { // base case: যোগফল ঠিক target
out.push([...path]); // snapshot!
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // PRUNE: পরের সবগুলোও বড় (sorted)
path.push(candidates[i]); // CHOOSE
go(i, path, remaining - candidates[i]); // EXPLORE (i: reuse allowed)
path.pop(); // UN-CHOOSE
}
};
go(0, [], target);
return out;
}
// ---- order-independent তুলনার helper ----
const norm = (lol) => JSON.stringify(lol.map(s => [...s].sort((a, b) => a - b)).sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));
// ---- test cases ----
assert(norm(combinationSum([2, 3, 6, 7], 7)) === norm([[2, 2, 3], [7]]), "main");
assert(norm(combinationSum([2, 3, 5], 8)) === norm([[2, 2, 2, 2], [2, 3, 3], [3, 5]]), "ex2");
assert(JSON.stringify(combinationSum([2], 1)) === JSON.stringify([]), "অসম্ভব");
assert(norm(combinationSum([1], 2)) === norm([[1, 1]]), "reuse 1+1");
assert(combinationSum([2, 3, 6, 7], 7).length === 2, "count");
assert(JSON.stringify(combinationSum([8], 7)) === JSON.stringify([]), "candidate > target");
console.log("সব JS test pass!");
```
> **JS টীকা:** তিনটা চাবি এক জায়গায় — `start` index duplicate সংগ্রহ ঠেকায়, `go(i, ...)` (i+1 নয়) একই সংখ্যা reuse-এর অনুমতি দেয়, আর sorted candidate-এ `candidates[i] > remaining` হলে `break` পুরো hopeless লেজ এক কোপে কাটে। `candidates.sort((a, b) => a - b)` দিতেই হবে — JS default sort সংখ্যাকে string ধরে, যা prune ভেঙে দিত। `remaining` integer কমিয়ে target-কেই recursion-এর state বানাই।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function combinationSum(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const out: number[][] = [];
const go = (start: number, path: number[], remaining: number): void => {
if (remaining === 0) {
out.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // PRUNE
path.push(candidates[i]); // CHOOSE
go(i, path, remaining - candidates[i]); // EXPLORE (reuse)
path.pop(); // UN-CHOOSE
}
};
go(0, [], target);
return out;
}
function expect