013 — Combination Sum II¶

Problem link ও উৎস

Original source: Classic backtracking exercise (target sum, each used once, with duplicates)
Platform: LeetCode — https://leetcode.com/problems/combination-sum-ii/
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

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

সংখ্যার একটা list candidates (যেখানে duplicate থাকতে পারে) আর একটা target দেওয়া আছে। তোমার কাজ: এমন সব distinct সংগ্রহ বের করা যাদের যোগফল ঠিক target — কিন্তু এবার প্রতিটা সংখ্যা (তার position ধরে) একবারই ব্যবহার করা যাবে, আর একই সংগ্রহ দুবার নয়। Combination Sum-এ reuse চলত আর সব আলাদা ছিল; এখানে reuse বন্ধ, আর input-এর duplicate থেকে যেন duplicate সংগ্রহ না আসে।

উদাহরণ

candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
combinations = [1,1,6], [1,2,5], [1,7], [2,6]   (প্রতিটা একবার, প্রতিটা সংখ্যা নিজ position-এ একবার)

Input ও output¶

উদাহরণ

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]]

চেনা উদাহরণে বোঝা¶

হাতের কিছু নির্দিষ্ট নোট (যার মধ্যে দুটো একই মানের নোট আছে) দিয়ে ঠিক একটা বিল মেটানোর কথা ভাবো — প্রতিটা নোট একবারই দেওয়া যায় (reuse নেই)। দুটো একই 1-টাকার নোট থাকলে "একটা 1 দিলাম" সিদ্ধান্তটা একই level-এ দুবার গোনার মানে নেই (একই ফল); কিন্তু একটা সংগ্রহে দুটো 1 দুটোই ব্যবহার করা বৈধ। এই সূক্ষ্ম পার্থক্যই i > start skip সামলায়।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত্তি দুটোর সংকর: 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।

ভেতরের যুক্তি¶

লুকানো logic দুটো আলাদা duplicate-উৎস সামলানো। (a) একই সংগ্রহ ভিন্ন order-এ — start-index দিয়ে বাড়ন্ত ক্রম চাপিয়ে দমন (Combinations থেকে)। (b) input-এ সমান মান একাধিক copy — sort করে একই level-এ দ্বিতীয় copy skip করে দমন (Subsets II থেকে)। দুটো ভিন্ন duplicate, দুটো ভিন্ন অস্ত্র — গুলিয়ে ফেললেই হয় নকল আসে নয় বৈধ সংগ্রহ হারায়।

কী দিয়ে তথ্য রাখব¶

একটা list path (বর্তমান সংগ্রহ), একটা list out (ফলাফল), একটা integer remaining (running complement), আর call stack। candidates.sort() অপরিহার্য — duplicate পাশাপাশি আনতে আর target-prune-এর break বৈধ করতে। record-এ path[:] snapshot।

এটি কেন উপযুক্ত¶

একটাই sort দুটো কাজ সারে: সমান মান পাশাপাশি (skip-line-এর প্রতিবেশী-তুলনা কাজ করে) আর বাড়ন্ত ক্রম (target ছাড়ালে break বৈধ)। remaining integer base case (==0) ও prune (> remaining) দুটোই O(1)-তে দেয়। path mutable বলে choose/un-choose O(1)। আলাদা seen-set লাগে না — পাশের প্রতিবেশীই duplicate বলে দেয়।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা position একবার-নাও/বাদ-দাও করে সব 2^nটা subset গড়ো (position-ভিত্তিক, তাই দুটো সমান copy আলাদা গোনা হবে); যেগুলোর যোগফল target সেগুলো রাখো; তারপর sort করে set-এ ফেলে duplicate সংগ্রহ ঝেড়ে ফেলো।

উদাহরণ

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)          # নকল সংগ্রহ ঝাড়

কোথায় বেশি কাজ হচ্ছে¶

এই version সবসময় পুরো 2^n subset গড়ে — target ছাড়িয়ে যাওয়া শাখাতেও গভীরে নামে — তারপর target-filter আর dedup-এ আরও কাজ। দুই অপচয়: hopeless শাখায় সময়, আর duplicate সংগ্রহ বারবার গড়ে পরে ঝাড়া। sort + target-prune (break) hopeless লেজ গাছেই কাটে, আর i > start skip duplicate সংগ্রহ গড়ার আগেই আটকায় — পরে ঝাড়ার দরকারই পড়ে না।

যে বিষয়টি খেয়াল করতে হবে¶

মূল 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 — এদের একটাও ভুললে হয় নকল নয় হারানো।

আরও কম কাজে সমাধান¶

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)।

ভাবনার পরিবর্তন¶

মোচড়: Combination Sum-এর কঙ্কালে ঠিক দুটো লাইন বদলাও — go(i) কে go(i+1) করো (reuse বন্ধ), আর loop-এর শুরুতে Subsets II-র skip-line বসাও (i > start সমান প্রতিবেশী)। নতুন কিছু আবিষ্কার নয়, দুটো আগের note-এর অংশ জোড়া লাগানো — এটাই inheritance-এর সৌন্দর্য।

ছবিতে বোঝা¶

ছোট পূর্ণ উদাহরণ: sorted input [1,1,2], target 3। প্রতিটি index সর্বোচ্চ একবার নেওয়া যায়।

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-এ ধাপে ধাপে¶

combination_sum2([10,1,2,7,6,1,5], 8) (sort: [1,1,2,5,6,7,10]):

go(0,[],8): i=0 (1): append → go(1,[1],7)।
go(1,[1],7): i=1 (1): append → go(2,[1,1],6): i=4 (6): record [1,1,6]...; pop চেইন।
go(1,[1],7): i=2 (2): → go(3,[1,2],5): i=3 (5): record [1,2,5]।
go(1,[1],7): i=5 (7): record [1,7]।
ফিরে go(0,[],8): i=1 (1) — i>start(0) ও সমান → skip। i=2 (2): → go(3,[2],6): i=4 (6): record [2,6]।
out = [[1,1,6],[1,2,5],[1,7],[2,6]] — 4টা distinct।

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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!।

খরচ ও সাধারণ ভুল¶

সময়¶

worst case O(2^n · n) — n position-এ নাও/বাদ-দাও, প্রতিটা বৈধ সংগ্রহের snapshot নিতে n; বাস্তবে target-prune + duplicate-skip গাছ অনেক ছোট করে। sort-এর O(n log n) নিচে চাপা।

অতিরিক্ত জায়গা¶

Output বাদ দিলে O(n) — call stack + path n পর্যন্ত গভীর। Output ধরলে সব সংগ্রহের মোট আকার।

যে ভুলগুলো এড়াতে হবে¶

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-এর প্রতিবেশী-তুলনা কাজ করে।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: Combination Sum (#12)-এর start-index + remaining + target-prune, আর Subsets II (#10)-এর sort-and-skip। ../patterns.md-এর Pattern 5-এ এটা তালিকাভুক্ত; skip-trick-এর শিকড় Pattern 3-এর শেষ লাইনে। দুই আগের note ভালো বুঝলে এই problem শুধু তাদের জোড়া।

পরের অনুশীলন¶

Combination Sum (reuse allowed, সব আলাদা) — https://leetcode.com/problems/combination-sum/ (এই tracker-এর #12)
Subsets II (sort-skip, target নেই) — https://leetcode.com/problems/subsets-ii/ (#10)
Permutations II (sorted skip, ordering সহ) — https://leetcode.com/problems/permutations-ii/ (#14)

কৌশলটি মনে রাখুন¶

Pruning + duplicate handling একসাথে: start-index (order-নকল দমন) + go(i+1) (reuse বন্ধ) + i > start সমান-প্রতিবেশী skip (value-নকল দমন) + sorted target-break (hopeless লেজ কাটা) — চারটা নিয়ম মিলে duplicate-সহ constraint enumeration-এর সম্পূর্ণ টুলকিট।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "Combination Sum II = Combination Sum-এর কঙ্কাল, কিন্তু go(i+1) (reuse নেই) + Subsets II-র i>start skip।" যখনই 'duplicate-সহ list, প্রতিটা একবার, target-এ পৌঁছাও, distinct সংগ্রহ' শুনবে — এই দুই-trick জোড়া skeleton মনে করবে; কোন duplicate-কে কোন অস্ত্রে মারছ সেটা স্পষ্ট রাখো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।