010 — Subsets II

Source

• 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

1. Problem in simple words

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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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,...] duplicate হয় না।

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

9. Brute force thinking

প্রথম সরল চিন্তা: সাধারণ 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]

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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।

13. Thinking tweak

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

14. Step-by-step dry run

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।

15. Python solution

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

16. Line-by-line code explanation

• 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 হবে না।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

• 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-এর নিয়ম, এখানে নয়)।

21. Which basic problem this inherits from

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

22. Similar harder problems

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

23. Pattern learned

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

24. Final summary

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