010 — Subsets II

Problem link ও উৎস

• Original source: Classic backtracking exercise (power set with duplicates)
• Platform: LeetCode — https://leetcode.com/problems/subsets-ii/
• Topic: recursion / backtracking (include/exclude + duplicate skip)
• Difficulty: Medium
• Pattern: include/exclude + duplicate skip — sort করে একই level-এ সমান প্রতিবেশী বাদ দাও
• Basic idea inherited from: Subsets + sort-and-skip

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

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

একটা সংখ্যার list nums দেওয়া আছে যেখানে duplicate থাকতে পারে। তোমার কাজ: এর সব distinct subset (power set) বের করা — কিন্তু একই subset দুবার নয়। সাধারণ Subsets-এ সব element আলাদা ছিল, তাই কোনো subset repeat হতো না; এখানে [1, 2, 2]-এর মতো input-এ সরল include/exclude করলে [1, 2] দুবার আসবে (দুটো ভিন্ন 2 থেকে)। সেই duplicate-গুলোই বাদ দিতে হবে।

উদাহরণ

nums = [1, 2, 2]
subsets = [], [1], [2], [1,2], [2,2], [1,2,2]   (মোট 6 distinct)

Input ও output

উদাহরণ

Input : [1, 2, 2] -> Output: [], [1], [2], [1,2], [2,2], [1,2,2]   (6 distinct)
Input : [0]       -> Output: [], [0]

Edge case 1 (সব সমান): [1, 1] -> Output: [], [1], [1,1]   (3টা)
Edge case 2 (খালি):    []     -> Output: [[]]

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

একগুচ্ছ মুদ্রা ভাবো যেখানে দুটো একই রকম 2-টাকা আছে। আলাদা সংগ্রহ বানাতে গেলে "একটা 2-টাকা" সংগ্রহটা দুবার গোনার মানে নেই — দুটো 2-টাকা দেখতে এক, তাই "2-টাকা নিলাম" সিদ্ধান্তটা একবারই গোনো। কোনগুলো নিচ্ছ সেটাই গুরুত্বপূর্ণ, কোন কপিটা নিচ্ছ তা নয়।

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

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

ভিত্তি হলো Subsets + sort-and-skip। কঙ্কাল হুবহু Subsets — প্রতিটা item নাও বা বাদ দাও — কিন্তু একটা বাড়তি নিয়ম: আগে list sort করো, যাতে সমান সংখ্যাগুলো পাশাপাশি আসে; তারপর কোনো level-এ একই মান দ্বিতীয়বার শুরু করার চেষ্টা করলে সেটা skip করো। এই sort-and-skip trick-টাই Combination Sum II-তেও আবার লাগবে।

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

লুকানো logic হলো canonical ordering দিয়ে duplicate দমন। sort করার পর প্রতিটা distinct subset শুধু একটাই বৈধ পথে তৈরি হয় — প্রথম available copy থেকে। একই value-র দ্বিতীয় copy দিয়ে নতুন একটা subset শুরু করলে সেটা আগেই-তৈরি কোনো subset-এর হুবহু নকল হবে, তাই ওই branch কেটে দিই। এতে count 2^n-এর বদলে distinct subset-সংখ্যায় নেমে আসে।

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

একটা list path (বর্তমান subset গড়তে), একটা list out (সব subset জমাতে), আর recursion-এর জন্য call stack। প্রথমে nums.sort() লাগে যাতে duplicate পাশাপাশি বসে। প্রতিটা node-এই একটা বৈধ subset, তাই record করার সময় path[:] snapshot।

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

sort করা list-এ সমান মান পাশাপাশি, তাই "এই level-এ এটা কি duplicate?" প্রশ্নের উত্তর শুধু nums[i] == nums[i-1] দেখেই O(1)-তে মেলে — আলাদা কোনো seen-set লাগে না, পাশের প্রতিবেশীই যথেষ্ট। path mutable বলে append/pop O(1), আর start-index দিয়ে loop চালালে প্রতিটা subset একটাই বাড়ন্ত ক্রমে গড়ে।

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

প্রথম সরল উপায়

প্রথম সরল চিন্তা: সাধারণ Subsets চালিয়ে 2^nটা subset গড়ো, তারপর প্রতিটাকে sort করে একটা set-এ (tuple আকারে) ফেলে duplicate ঝেড়ে ফেলো।

উদাহরণ

all = subsets(nums)                 # 2^n, duplicate সহ
unique = set(tuple(sorted(s)) for s in all)
out = [list(t) for t in unique]

কোথায় বেশি কাজ হচ্ছে

এই version সবসময় পুরো 2^nটা subset গড়ে, এমনকি অর্ধেক যদি duplicate হয়ও — তারপর hashing দিয়ে ছেঁকে ফেলে। কাজ নষ্ট হয় দুবার: একই subset বারবার তৈরি, আবার dedup-এর জন্য বাড়তি O(n) করে hashing। sort-and-skip version duplicate branch-এ ঢোকেই না, তাই সরাসরি distinct subset-গুলোই গড়ে — গড়ার সময়ই pruning, পরে ঝাড়াই নয়।

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

মূল observation: sort করলে duplicate পাশাপাশি, আর তখন duplicate দমনের নিয়ম একলাইন — "একই level-এ (একই start থেকে) একই মান দ্বিতীয়বার শুরু কোরো না।" i > start and nums[i] == nums[i-1] ঠিক এই "একই level-এ দ্বিতীয় copy" অবস্থাটা ধরে। লক্ষ্য করো শর্তটা i > start, i > 0 নয় — গভীরে যাওয়ার সময় সমান copy নেওয়া বৈধ ([2,2]), শুধু একই level-এ পাশাপাশি নতুন শুরু বারণ।

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

nums.sort() করো। go(start, path): ঢোকার সাথে সাথে path-এর snapshot record করো (প্রতিটা node একটা বৈধ subset)। তারপর i start থেকে শেষ পর্যন্ত: যদি i > start and nums[i] == nums[i-1] হয় skip; নাহলে append (choose), go(i+1, path) (explore), pop (un-choose)। i+1 কারণ প্রতিটা item একবারই। এটাই Subsets-এর start-index রূপ + একটা skip-line।

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

মোচড়: duplicate ঠেকাতে hashing/set-এর কথা ভেবো না; বরং sort করে নাও, তারপর একই level-এ সমান প্রতিবেশী এড়িয়ে যাও। duplicate সমস্যা তখন একটা locality সমস্যায় নেমে আসে — শুধু পাশের element-এর সাথে তুলনা, পুরো ইতিহাস মনে রাখার দরকার নেই।

ছবিতে বোঝা

sort করা [1, 2, 2]-এ start-index loop; একই level-এ দ্বিতীয় 2 skip:

উদাহরণ

                       go(0, [])  -> record []
        1 /              2 |            2 (skip: প্রতিবেশী সমান)
   go(1,[1])         go(2,[2])
   record[1]         record[2]
     2 |               2 |
 go(2,[1,2])      go(3,[2,2])
 record[1,2]      record[2,2]
     2 |
 go(3,[1,2,2])
 record[1,2,2]

root-এর তৃতীয় branch (দ্বিতীয় 2) skipped -> [2] বা [2,2] duplicate হয় না।

ছোট input-এ ধাপে ধাপে

subsets_with_dup([1, 2, 2]) (sort করা: [1, 2, 2]), go(start, path):

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

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

Python

Python

def subsets_with_dup(nums):
    nums.sort()                       # duplicate পাশাপাশি আনতে sort
    out = []
    def go(start, path):
        out.append(path[:])           # প্রতিটা node একটা বৈধ subset (snapshot)
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue              # একই level-এ সমান প্রতিবেশী -> skip
            path.append(nums[i])      # CHOOSE
            go(i + 1, path)           # EXPLORE (i+1: প্রতিটা item একবার)
            path.pop()                # UN-CHOOSE
    go(0, [])
    return out

# ---- order-independent তুলনার helper ----
def norm(list_of_lists):
    return sorted([sorted(s) for s in list_of_lists])

# ---- tests ----
assert norm(subsets_with_dup([1, 2, 2])) == norm(
    [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]])
assert len(subsets_with_dup([1, 2, 2])) == 6
assert norm(subsets_with_dup([0])) == norm([[], [0]])
assert norm(subsets_with_dup([1, 1])) == norm([[], [1], [1, 1]])
assert len(subsets_with_dup([1, 1])) == 3        # duplicate দমন কাজ করছে
assert subsets_with_dup([]) == [[]]              # খালি -> শুধু খালি subset
print("সব test pass!")

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

• nums.sort() — সমান মান পাশাপাশি, যাতে প্রতিবেশী-তুলনা কাজ করে।
• out.append(path[:]) — এই node-এর subset-এর snapshot; প্রতি node-ই বৈধ।
• for i in range(start, len(nums)): — start থেকে শুরু, যাতে প্রতিটা subset একটাই বাড়ন্ত ক্রমে।
• if i > start and nums[i] == nums[i-1]: continue — একই level-এ duplicate value-র দ্বিতীয় copy skip।
• path.append(nums[i]) / go(i+1, path) / path.pop() — choose → explore → un-choose; i+1 মানে item আর reuse হবে না।

Output মিলিয়ে দেখা

subsets_with_dup([1,2,2]): প্রতি recursive node-এ একটা subset record হয়; skip-line root-এ দ্বিতীয় 2-এর branch কেটে দেয়, তাই [2]/[2,...] একবারই আসে। ফল 6টা distinct subset। order নির্ভরযোগ্য নয় (inner order-ও গুরুত্বহীন), তাই norm-এ sorted-of-sorted করে তুলনা — তাই assert stable। [1,1]-এ 3টা, খালি-তে [[]]। সব মিলে print: সব test pass!।

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

সময়

O(n · 2^n) worst case (সব আলাদা হলে) — distinct subset যত, প্রতিটার snapshot নিতে n; duplicate থাকলে subtree pruning-এ আরও কম। sort-এর O(n log n) এর নিচে চাপা পড়ে।

অতিরিক্ত জায়গা

Output বাদ দিলে O(n) — path ও call stack-এর গভীরতা n। Output ধরলে distinct subset × n।

যে ভুলগুলো এড়াতে হবে

• sort না করা — duplicate ছড়িয়ে থাকে, প্রতিবেশী-তুলনা ব্যর্থ, repeat subset বেরোয়।
• skip-শর্তে i > 0 লেখা (i > start-এর বদলে) — তখন [2,2]-এর মতো বৈধ subset-ও কেটে যায়; গভীরে সমান copy নেওয়া বৈধ, শুধু একই level-এ পাশাপাশি নতুন শুরু বারণ।
• out.append(path) snapshot ছাড়া — সব entry একই live list-এর reference।
• go(i+1)-এর বদলে go(i) — item reuse হয়ে যায় (ওটা Combination Sum-এর নিয়ম, এখানে নয়)।

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

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

ভিত্তি: Subsets (এই tracker-এর #7)-এর include/exclude, এখানে sort-and-skip যোগ করে। ../patterns.md-এর Pattern 3-এর শেষে বলা আছে "sort করো, তারপর EXCLUDE পাশে সমান প্রতিবেশীদের skip করো" — এই note সেটারই পূর্ণ রূপ। একই skip-trick পরে Combination Sum II (#13)-তে ফিরবে।

পরের অনুশীলন

• Combination Sum II (sort-and-skip + target) — https://leetcode.com/problems/combination-sum-ii/ (এই tracker-এর #13)
• Permutations II (sorted skip, ordering সহ) — https://leetcode.com/problems/permutations-ii/ (#14)
• Combinations (fixed size k) — https://leetcode.com/problems/combinations/ (#11)

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

Sort-and-skip duplicate handling: sort করে সমান মান পাশাপাশি আনো, তারপর একই recursion-level-এ i > start and nums[i]==nums[i-1] হলে skip — distinct enumeration-এর সর্বজনীন trick, যা subsets/combinations/permutations সবেই খাটে।

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

ভবিষ্যতের আমাকে: "Subsets II = Subsets-এর start-index version + sort + i>start হলে সমান প্রতিবেশী skip।" যখনই 'duplicate input থেকে distinct combination/subset' শুনবে — sort করে নাও, একই level-এ সমান প্রতিবেশী এড়াও; set দিয়ে পরে ঝাড়ার চেয়ে এটা পরিষ্কার ও দ্রুত।

---

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