017 — Partition Equal Subset Sum¶

Source¶

Original source: Classic cross-topic capstone interview problem (subset-sum / 0-1 knapsack family)
Platform: LeetCode — https://leetcode.com/problems/partition-equal-subset-sum/
Topic: dynamic programming + math
Difficulty: Medium
Pattern: Subset-sum DP (0-1 knapsack, boolean reachability)
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 12 dynamic programming (কোন কোন sum বানানো সম্ভব, তার একটা boolean table) আর 01 math (sum-এর parity দিয়ে আগে থেকেই অসম্ভব case ছেঁটে ফেলা)। দুই tool জোড়া লাগলেই subset-sum।

1. Problem in simple words¶

তোমাকে একটা positive integer-এর array দেওয়া আছে। তোমার কাজ: বলো এটাকে দুই ভাগে ভাগ করা যায় কিনা, যাতে দুই ভাগের যোগফল সমান হয়। প্রতিটা সংখ্যা ঠিক একটা ভাগে যাবে। শুধু True/False চাই।

nums : [1, 5, 11, 5]
ভাগ : {11} আর {1, 5, 5}  -> দুটোরই sum = 11  -> True

2. Which basic idea does this inherit from?¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

12 dynamic programming থেকে: "কোন কোন subset-sum বানানো সম্ভব" — 0 থেকে target পর্যন্ত প্রতিটা sum-এর জন্য একটা boolean reachability state রাখা (0-1 knapsack-এর রূপ)।
01 math থেকে: একটা সহজ সংখ্যাতাত্ত্বিক pruning — মোট sum যদি odd হয়, সমান দু'ভাগ অসম্ভব (অর্ধেক integer হবে না)। তাই DP শুরুর আগেই অর্ধেক case বাদ।

একা DP তোমাকে দেয় সব subset না ঘুরে "কোন sum সম্ভব" জানার ক্ষমতা; একা math দেয় শুরুতেই অসম্ভব case ছাঁটার ক্ষমতা। দুটো মিললে O(n × target)।

3. What is the hidden math or logic?¶

প্রথম math: যদি দুই ভাগ সমান হয়, প্রতিটার sum হবে total / 2। তাই total odd হলেই উত্তর False — কোনো subset-ই অর্ধেক বানাতে পারবে না। total even হলে problem-টা দাঁড়ায়: "এমন একটা subset আছে কি, যার sum ঠিক target = total / 2?" — কারণ সেই subset পেলে বাকিরাও আপনা থেকেই target হবে।

লুকানো DP logic একটা reachability: dp[s] = "এ পর্যন্ত দেখা সংখ্যা দিয়ে ঠিক s sum বানানো সম্ভব কি?" প্রতিটা নতুন num-এ, আগে যত sum সম্ভব ছিল, তাদের প্রতিটার সাথে num যোগ করেও নতুন sum সম্ভব হয়:

dp[s] হয়ে যায় True যদি dp[s - num] আগে True থাকে

4. Which data structure is needed?¶

একটা 1D boolean array dp, length target + 1। dp[s] ধরে রাখে "s বানানো যায় কিনা"। এটাই 12 DP-র knapsack table; 01 math শুধু target নির্ধারণ আর parity-ছাঁটে সাহায্য করে।

5. Why this data structure fits¶

আমাদের জানতে হবে শুধু "অমুক sum কি reachable" — হ্যাঁ/না। তাই পুরো subset store করার দরকার নেই, প্রতিটা সম্ভাব্য sum-এর জন্য একটা boolean (12 DP) যথেষ্ট। sum-গুলো 0..target পর্যন্ত ছোট ও পরপর integer, তাই array-ই নিখুঁত — O(1) index। আর target নিজে total/2, যা math (01) দেয়; total odd হলে array বানানোর আগেই বেরিয়ে যাই।

6. Real-life analogy¶

ভাবো তোমার কিছু আলাদা ওজনের বাটখারা আছে, আর তুমি দু'পাল্লার দাঁড়িপাল্লা ঠিক ভারসাম্যে আনতে চাও। আগে মোট ওজন মাপো — বিজোড় হলে সমান দু'ভাগ অসম্ভব, চেষ্টাই করো না (এটাই parity-shortcut)। জোড় হলে তুমি কেবল দেখতে চাও: কিছু বাটখারা বেছে এক পাল্লায় ঠিক "অর্ধেক ওজন" তোলা যায় কিনা — পারলেই বাকিগুলো অন্য পাল্লায় সমান হবে।

7. Visual explanation¶

nums = [1, 5, 11, 5], total = 22, target = 11। dp (reachable sums) বদলায়:

শুরু:                dp[0]=T, বাকি সব F   (শূন্য sum সবসময় সম্ভব)

num=1:  s=1 <- dp[0]                       reachable: {0,1}
num=5:  s=6 <-dp[1], s=5 <-dp[0]          reachable: {0,1,5,6}
num=11: s=11<-dp[0], s=12.. (target পার)  reachable: {0,1,5,6,11,...}
        -> dp[11] = True!  (শুধু {11} দিয়েই)
num=5:  আরও sum reachable হয়, কিন্তু dp[11] আগেই True

dp[target=11] = True   ->  উত্তর True

8. Example input and output¶

Input : nums = [1, 5, 11, 5]   -> Output: True    # {11} আর {1,5,5}
Input : nums = [1, 2, 3, 5]    -> Output: False   # total=11 (odd) -> অসম্ভব

Edge case 1 (দুটো সমান): nums = [1, 1]      -> Output: True   # {1} আর {1}
Edge case 2 (একটা সংখ্যা): nums = [1]       -> Output: False  # ভাগ করার মতো কিছু নেই

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা সংখ্যার জন্য দুটো পছন্দ — subset-এ নাও বা নিও না। সব combination ঘুরে দেখো কোনোটার sum target হয় কিনা।

def can(i, s):
    if s == target: return True
    if i == n or s > target: return False
    return can(i+1, s + nums[i]) or can(i+1, s)   # নাও / নিও না

10. Why brute force is slow¶

প্রতিটা element-এ দুটো branch — মোট O(2^n) combination। memo ছাড়া একই (i, s) জোড়া বহুবার ফিরে আসে। যেমন আলাদা পথে একই running sum তৈরি হয়, প্রতিবার নতুন করে গণনা হয়। এই পুনরাবৃত্তিই 12 DP দূর করে — 0..target প্রতিটা sum মাত্র একবার "reachable কিনা" হিসাব করে।

11. Key observation¶

দুটো observation একসাথে: (১) math — total odd হলে উত্তর সাথে সাথে False, কোনো কাজ লাগে না। (২) DP — কোন কোন sum reachable, তা subset কোন order-এ বাছছ তার উপর নির্ভর করে না; শুধু "এ পর্যন্ত কোন sums বানানো যায়" — এই boolean set-টাই যথেষ্ট, প্রকৃত subset লাগে না। এই দুই observation মিলে exponential search-টাকে O(n × target)-এ নামায়।

12. Optimized intuition¶

আগে total বের করো; odd হলে False। নাহলে target = total // 2। একটা boolean dp নাও, dp[0] = True। প্রতিটা num-এর জন্য sum-গুলো উঁচু থেকে নিচু (target → num) scan করে dp[s]-কে dp[s] or dp[s - num] করো — উঁচু-থেকে-নিচু order একটা num দুবার ব্যবহার হওয়া আটকায় (0-1 knapsack, প্রতিটা একবার)। শেষে dp[target]-ই উত্তর।

13. Thinking tweak¶

মোচড়: "দুই ভাগে কীভাবে ভাঙব" ভাবার বদলে ভাবো "মোটের ঠিক অর্ধেক sum-এর একটা subset আছে কি?" — একটা ভাগ পেলেই বাকিটা free। আর "কোন কোন subset" নয়, শুধু "কোন কোন sum reachable" — এই boolean-এ নামালেই exponential চলে যায়।

14. Step-by-step dry run¶

nums = [1, 5, 5], total = 11 (odd) → সরাসরি False। এবার একটা even case nums = [2, 2, 1, 1], total = 6, target = 3:

শুরু: dp = [T, F, F, F] (index 0..3)
num=2: s=3 <- dp[1]?F; s=2 <- dp[0]?T → dp[2]=T। now {0,2}
num=2: s=3 <- dp[1]?F; s=2 <- dp[0]?T (already)। now {0,2}
num=1: s=3 <- dp[2]?T → dp[3]=T; s=1 <- dp[0]?T → dp[1]=T। now {0,1,2,3}
dp[target=3] = True → return True (যেমন {2,1})

15. Python solution¶

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:               # 01 math: odd মোট -> সমান দু'ভাগ অসম্ভব
        return False
    target = total // 2
    dp = [False] * (target + 1)      # dp[s] = s বানানো সম্ভব?
    dp[0] = True                     # শূন্য sum সবসময় সম্ভব
    for num in nums:
        for s in range(target, num - 1, -1):   # উঁচু->নিচু: প্রতিটা num একবার
            if dp[s - num]:
                dp[s] = True
    return dp[target]

# ---- tests ----
assert can_partition([1, 5, 11, 5]) == True     # {11} | {1,5,5}
assert can_partition([1, 2, 3, 5]) == False     # total 11 (odd)
assert can_partition([1, 1]) == True            # {1} | {1}
assert can_partition([2, 2, 1, 1]) == True      # {2,1} | {2,1}
assert can_partition([1]) == False              # ভাগ করার মতো নেই
assert can_partition([3, 3, 3, 4, 5]) == True   # {3,3,3} | {4,5} = 9
print("সব test pass!")

16. Line-by-line code explanation¶

total = sum(nums) — পুরো array-র যোগফল; অর্ধেকটাই হবে target।
if total % 2 != 0: return False — 01 math-এর parity shortcut; odd হলে আর কিছু করার নেই।
target = total // 2 — একটা subset-কে ঠিক এতটুকু sum বানাতে হবে।
dp = [False] * (target + 1) — সব sum শুরুতে unreachable।
dp[0] = True — কিছু না নিয়েই sum 0 বানানো যায় (base case)।
for num in nums — প্রতিটা সংখ্যা একবার বিবেচনা (0-1 knapsack-এর item loop)।
for s in range(target, num - 1, -1) — sum উঁচু থেকে নিচু; এই উল্টো order একই num-কে দুবার যোগ হওয়া আটকায় (প্রতিটা item একবার)।
if dp[s - num]: dp[s] = True — আগে s - num reachable হলে এখন num যোগ করে s-ও reachable।
return dp[target] — অর্ধেক sum বানানো গেল কিনা — সেটাই উত্তর।

17. Output walkthrough¶

[1,5,11,5]-এ total=22 even, target=11। num=11 প্রক্রিয়া করার সময় dp[11] dp[0] (True) থেকে True হয়ে যায় — অর্থাৎ শুধু {11} দিয়েই অর্ধেক, return True, assert pass। [1,2,3,5]-এ total=11 odd, প্রথম লাইনেই return False। [1]-এ total=1 odd → False। even-case গুলোতে DP dp[target] ঠিকভাবে True/False দেয়। শেষে print: সব test pass!।

18. Time complexity¶

O(n × target) — প্রতিটা সংখ্যা (n-টা) প্রতিবার 0..target sum range scan করে। target = total/2, তাই pseudo-polynomial (মানের উপর নির্ভর)।

19. Space complexity¶

O(target) — একটা মাত্র 1D boolean array, length target + 1। 2D table-ও সম্ভব, কিন্তু এক-সারির rolling form (উঁচু→নিচু loop) দিয়ে শুধু এক row রাখলেই চলে।

20. Common mistakes¶

parity-check বাদ দেওয়া — odd total-এ অযথা DP চালানো (ভুল না, কিন্তু target = total//2 floor-এ ভুল উত্তরও দিতে পারে)।
inner loop নিচু থেকে উঁচু চালানো — তখন একই num একাধিকবার যোগ হয়ে যায়, এটা unbounded knapsack হয়ে যায়, 0-1 না; উঁচু→নিচু-ই ঠিক।
dp[0] = True সেট না করা — base ছাড়া কোনো sum-ই reachable হবে না।
target-কে total / 2 (float) রাখা — integer total // 2 ব্যবহার করো, নাহলে index ভাঙবে।

21. Which basic problem this inherits from¶

ভিত্তি: কোন কোন sum reachable, তার boolean DP table (12 DP-র ../../12-dynamic-programming/patterns.md, 0-1 knapsack family) + parity/divisibility দিয়ে আগেই অসম্ভব case ছাঁটা (01 math-এর ../../01-math-based-programming-fundamentals/)। এই দুটো cold অবস্থায় জানা থাকলে subset-sum নিজে থেকেই দাঁড়িয়ে যায়।

22. Similar harder problems¶

Target Sum (প্রতিটা সংখ্যার আগে +/- বসিয়ে target — একই subset-sum, কিন্তু count চায়) — https://leetcode.com/problems/target-sum/
Last Stone Weight II (দুই ভাগের পার্থক্য minimize, subset-sum-এর variant) — https://leetcode.com/problems/last-stone-weight-ii/
Partition to K Equal Sum Subsets (দুই নয়, k ভাগ — DP + bitmask লাগে) — https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

23. Pattern learned¶

Subset-sum / 0-1 knapsack boolean DP: "কিছু item বেছে ঠিক target sum বানানো যায় কি?" — dp[s] |= dp[s-num] দিয়ে reachable-sum set বানিয়ে O(n × target)-এ উত্তর; প্রতিটা item একবার রাখতে inner loop উঁচু→নিচু। সাথে math-এর parity prune। DP + math combo-র canonical রূপ।

24. Final summary¶

ভবিষ্যতের আমাকে: "দুই (বা সমান) ভাগে ভাঙা যায় কি" দেখলেই subset-sum মনে করবে — আগে total-এর parity check (odd হলেই False), তারপর target = total/2-এর জন্য boolean reachability DP। inner loop উঁচু থেকে নিচু রাখতে ভুলো না, নাহলে item দুবার গোনা হয়ে 0-1 ভেঙে যায়। DP table আর math-shortcut-এর সবচেয়ে পরিষ্কার মেলবন্ধন।

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