017 — Partition Equal Subset Sum¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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।

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

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

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

উদাহরণ

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

Input ও 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  # ভাগ করার মতো কিছু নেই

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

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

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

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

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

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

প্রথম 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 থাকে

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

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

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

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

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

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

প্রথম সরল চিন্তা: প্রতিটা সংখ্যার জন্য দুটো পছন্দ — 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)   # নাও / নিও না

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

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

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

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

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

আগে 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]-ই উত্তর।

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

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

ছবিতে বোঝা¶

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] update          reachable: {0,1,5,6,11}
        11-এর বড় sum table-এ নেই; target=11 পর্যন্তই রাখি।
        -> dp[11] = True!  (শুধু {11} দিয়েই)
num=5:  descending update শেষে reachable: {0,1,5,6,10,11}
        dp[11] = True থাকে; 1+5+5 দিয়েও 11 হয়।

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

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

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

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

Python¶

Python

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

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

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 বানানো গেল কিনা — সেটাই উত্তর।

Output মিলিয়ে দেখা¶

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

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

সময়¶

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

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

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

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

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 ভাঙবে।

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

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

ভিত্তি: কোন কোন 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 নিজে থেকেই দাঁড়িয়ে যায়।

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

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/

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

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 রূপ।

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

ভবিষ্যতের আমাকে: "দুই (বা সমান) ভাগে ভাঙা যায় কি" দেখলেই 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।