013 — Combination Sum II¶

Source¶

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

1. Problem in simple words¶

সংখ্যার একটা 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-এ একবার)

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 বলে দেয়।

6. Real-life analogy¶

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

7. Visual explanation¶

sort করা [1, 1, 2, 5, 6, 7, 10], target 8; একই level-এ দ্বিতীয় 1 skip:

                     go(0, [], 8)
       1 /            1 (skip: i>start, সমান)        2 | ...
  go(1,[1],7)
   1/  2| 5| 6| 7=record[1,7]
go(2,[1,1],6)  go(3,[1,2],5)  ...  go(.,[1,7],0)=record[1,7]
  ... 6=record[1,1,6]      5=record[1,2,5]

root-এর দ্বিতীয় 1-branch skipped, কিন্তু গভীরে [1,1,...] বৈধ (i>start তখন মেটে না)।
remaining==0 -> record; candidate>remaining -> break।

8. Example input and 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]]

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা 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)          # নকল সংগ্রহ ঝাড়

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-এর সৌন্দর্য।

14. Step-by-step dry run¶

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।

15. Python solution¶

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।

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

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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)

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।