013 — Partition Equal Subset Sum¶

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

Problem link ও উৎস

Original source: Classic 0/1 subset-sum (boolean) exercise
Platform: LeetCode — https://leetcode.com/problems/partition-equal-subset-sum/
Topic: dynamic programming
Difficulty: Medium
Pattern: Subset-sum (0/1, boolean)
Basic idea inherited from: Knapsack skeleton — "প্রতিটা item নাও বা বাদ দাও," কিন্তু value-র বদলে boolean reachability

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

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

একটা positive integer-এর array nums দেওয়া। প্রশ্ন: array-টাকে কি দুটো ভাগে এমনভাবে ভাঙা যায় যাতে দুই ভাগের যোগফল সমান হয়? শুধু "হ্যাঁ/না" (boolean) বলতে হবে। সমান দুই ভাগ মানে প্রতিটা ভাগের sum = মোট sum-এর অর্ধেক — তাই আসল প্রশ্ন হয়ে দাঁড়ায়: "এমন কোনো subset আছে কি যার sum ঠিক total / 2?"

উদাহরণ

nums = [1, 5, 11, 5]
মোট = 22, অর্ধেক = 11
subset {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  (মোট 11, বিজোড়)
Input : nums = [1,1]       -> Output: True   ({1} ও {1})

Edge case 1: nums = [1]        -> Output: False  (মোট 1, বিজোড়)
Edge case 2: nums = [2,2,2,2]  -> Output: True   ({2,2} ও {2,2})

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

ভাবো তোমার কাছে কিছু ওজনের বাটখারা, আর তুমি দুই পাল্লার দাঁড়িপাল্লা ঠিক balance করতে চাও। মোট ওজন বিজোড় হলে কখনো balance হবে না। নয়তো এক পাল্লায় ঠিক অর্ধেক ওজন তুলতে হবে। প্রতিটা বাটখারার সামনে সিদ্ধান্ত: "এটা বাঁ পাল্লায় রাখব, না রাখব না?" — যদি কোনো বাছাইয়ে বাঁ পাল্লা ঠিক অর্ধেকে দাঁড়ায়, balance সম্ভব।

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

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

ভিত্তি 0/1 knapsack-এর কঙ্কাল: প্রতিটা item-এ একটা binary সিদ্ধান্ত — নাও বা বাদ দাও, আর প্রতিটা item সর্বোচ্চ একবার। তফাত: knapsack value maximize করে, এখানে আমরা শুধু জানতে চাই একটা নির্দিষ্ট sum পৌঁছানো যায় কি না (boolean reachability)। তাই dp value নয়, True/False ধরে। "একবারই নেওয়া যায়" নিয়মটা loop-direction (right-to-left) দিয়ে enforce হয়।

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

লুকানো logic দুই ধাপ। (১) মোট sum বিজোড় হলে সমান দুই ভাগ অসম্ভব — সঙ্গে সঙ্গে False। (২) নয়তো target = total / 2 ঠিক করে জিজ্ঞেস করো: কিছু item বেছে ঠিক target বানানো যায় কি? প্রতিটা item-এ সিদ্ধান্ত — এটা subset-এ নিলে দরকার কমে target - nums[i], না নিলে target অপরিবর্তিত। যেকোনো একটা পথ target == 0-এ পৌঁছালেই True।

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

একটা 1D boolean array dp (size target + 1), dp[s] = এখন পর্যন্ত দেখা item দিয়ে sum s বানানো সম্ভব কি না। Top-down করলে একটা dict (state (i, rem) → bool)।

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

State: কোন item পর্যন্ত বিবেচনা করেছি, আর কত sum বানাতে বাকি। 1D-তে compress করলে শুধু "sum s reachable কি না" রাখি, কারণ item একে একে process করার সময় আগের item-এর reachable sum-গুলোই দরকার। boolean যথেষ্ট — আমরা পরিমাণ নয়, সম্ভাব্যতা track করছি। 0/1 নিশ্চিত করতে inner loop right-to-left, যাতে প্রতিটা item একবারই গোনা হয়।

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

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

প্রথম সরল চিন্তা: প্রতিটা item-এ recurse করে দুটো শাখা — এই item subset-এ নাও (target কমাও), বা বাদ দাও।

উদাহরণ

can(i, rem):                     # item i থেকে শুরু করে rem বানানো যায়?
    if rem == 0: return True
    if i == n or rem < 0: return False
    return can(i+1, rem - nums[i])   # নাও
        or can(i+1, rem)             # বাদ দাও
answer = can(0, total // 2)   (total বিজোড় হলে সরাসরি False)

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

এই recursion O(2^n) — প্রতিটা item-এ দুটো শাখা, মোট সব subset (2^n)। একই (i, rem) জোড়া বহু পথ দিয়ে বারবার পৌঁছানো হয় (overlapping subproblems)। 30+ item হলেই subset-সংখ্যা বিস্ফোরিত হয়।

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

মূল observation: distinct state মাত্র n × target-টা ((i, rem) জোড়া)। প্রতিটার উত্তর একবার গুনে রাখলে exponential subset-search polynomial (pseudo-polynomial, O(n × target)) হয়ে যায়। 1D-তে এটা আরও ছোট: শুধু কোন sum reachable তা track করি।

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

State (শব্দে): dp[s] = এখন পর্যন্ত process করা item-গুলোর কোনো subset দিয়ে ঠিক sum s বানানো সম্ভব কি না (boolean)। (Top-down-এ: can(i, rem) = item i..n-1 থেকে rem বানানো যায় কি না।)

Transition:

উদাহরণ

নতুন item x-এর জন্য (1D, right-to-left):
    dp[s] = dp[s]  or  dp[s - x]      for s = target down to x

কারণ: sum s হয় x ছাড়াই reachable ছিল (dp[s]), নয় x যোগ করে s - x থেকে (dp[s-x])।

Base case: dp[0] = True (খালি subset দিয়ে sum 0 সবসময় সম্ভব)। আগে check: total বিজোড় হলে সরাসরি False।

Answer location: dp[target], যেখানে target = total // 2।

Memoization (top-down): উপরের can(i, rem) recursion, dict যোগ। Tabulation (bottom-up): প্রতিটা item নিয়ে inner loop ডান-থেকে-বাঁ — এই direction-ই 0/1 নিশ্চিত করে (প্রতিটা item একবার)। বাঁ-থেকে-ডান করলে নিঃশব্দে unbounded হয়ে যেত।

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

মোচড়: "দুই ভাগে ভাঙব" — এই দ্বি-পক্ষীয় চিন্তা বাদ দিয়ে এক-পক্ষীয় করো: "একটা ভাগের sum যদি total/2 হয়, বাকিটা এমনিই total/2।" তাই দুই-ভাগ problem একটা single subset-sum reachability problem-এ পরিণত হয়। আর knapsack-এর সবচেয়ে কুখ্যাত নিয়ম এখানেই শিখি: 0/1 = inner loop ডান-থেকে-বাঁ।

ছবিতে বোঝা¶

dp[s] = sum s reachable কি না (T/F)। nums = [1, 5, 11, 5], target = 11:

উদাহরণ

শুরুতে: dp[0]=T, বাকি সব F

item 1 (=1):   reachable sums: {0, 1}
item 2 (=5):   {0, 1, 5, 6}
item 3 (=11):  {0, 1, 5, 6, 11}            <- 11 পৌঁছে গেছে!
item 4 (=5):   {0, 1, 5, 6, 10, 11, 16->skip>11}

প্রতিটা নতুন item x-এ, ডান-থেকে-বাঁ:
  for s from target down to x:
      dp[s] = dp[s] or dp[s - x]

s=11 হয়ে গেছে T -> answer True

ডান-থেকে-বাঁ যাওয়াটা জরুরি: একই item দুবার গোনা আটকায় (0/1)। বাঁ-থেকে-ডান গেলে একই item বহুবার ব্যবহৃত হয়ে যেত (unbounded)।

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

nums = [2, 2, 2, 2], total = 8, target = 4, 1D tabulation:

dp = [T, F, F, F, F] (dp[0]=T)
item 2: s=4→dp[2]? F; s=3→dp[1]? F; s=2→dp[0]=T → dp[2]=T → dp=[T,F,T,F,F]
item 2: s=4→dp[2]=T → dp[4]=T; s=2→dp[0]=T (already) → dp=[T,F,T,F,T]
item 2, item 2: dp[4] already T, কিছু বদলায় না
return dp[4] = True

হাতে মিলিয়ে: {2,2} আর {2,2} — দুই ভাগ সমান। ✔

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

Python¶

Python

# ---- way 1: memoization (top-down) ----
def can_partition_memo(nums):
    total = sum(nums)
    if total % 2 != 0:                       # বিজোড় হলে অসম্ভব
        return False
    target = total // 2
    n = len(nums)
    memo = {}
    def can(i, rem):                         # item i..n-1 থেকে rem বানানো যায়?
        if rem == 0:
            return True
        if i == n or rem < 0:
            return False
        if (i, rem) in memo:
            return memo[(i, rem)]
        memo[(i, rem)] = can(i + 1, rem - nums[i]) or can(i + 1, rem)
        return memo[(i, rem)]
    return can(0, target)

# ---- way 2: tabulation (bottom-up, 1D, right-to-left = 0/1) ----
def can_partition_tab(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True                             # খালি subset
    for x in nums:
        for s in range(target, x - 1, -1):   # ডান-থেকে-বাঁ -> প্রতিটা item একবার
            if dp[s - x]:
                dp[s] = True
    return dp[target]

# ---- tests ----
cases = [
    ([1, 5, 11, 5], True),
    ([1, 2, 3, 5], False),
    ([1, 1], True),
    ([1], False),
    ([2, 2, 2, 2], True),
    ([100], False),
    ([3, 3, 3, 4, 5], True),     # total 18, target 9: 4+5 বা 3+3+3
    ([1, 2, 5], False),          # total 8, target 4: পৌঁছানো যায় না
]
for nums, want in cases:
    assert can_partition_memo(nums) == want, (nums, can_partition_memo(nums))
    assert can_partition_tab(nums) == want, (nums, can_partition_tab(nums))

print("সব test pass!")

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

can_partition_memo: আগে বিজোড়-sum check; can(i, rem) item i থেকে শুরু করে rem বানানো যায় কি না; rem==0 → True, শেষ/negative → False; memo repeated কাজ এড়ায়।
can_partition_tab: dp[0]=True; প্রতিটা item-এ inner loop ডান-থেকে-বাঁ — এতেই 0/1 (একবার নেওয়া) নিশ্চিত হয়; dp[s] = dp[s] or dp[s-x]; answer dp[target]।
দুই function-ই বিজোড় মোট sum-এ সরাসরি False দেয় (অর্ধেক integer হয় না)।

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

cases-এ আটটা input — LeetCode-এর True/False জোড়া, সহজ [1,1] True, single-element [1] False, all-equal [2,2,2,2] True, একটা বড় [3,3,3,4,5] True (দুই রকম partition), আর একটা সম-মোট কিন্তু unreachable [1,2,5] False। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: সব test pass!।

JavaScript ও test cases¶

Subset-sum reachability total/2; 1D boolean, inner loop ডান-থেকে-বাঁ (0/1)। বিজোড় হলে সরাসরি false।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[s] = sum s reachable কি না; ডান-থেকে-বাঁ -> প্রতিটা item একবার
function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;          // বিজোড় -> অসম্ভব
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;                               // খালি subset
  for (const x of nums) {
    for (let s = target; s >= x; s--) {        // ডান-থেকে-বাঁ
      if (dp[s - x]) dp[s] = true;
    }
  }
  return dp[target];
}
// ---- test cases (example + edge) ----
const cases = [
  [[1, 5, 11, 5], true],
  [[1, 2, 3, 5], false],                      // মোট 11, বিজোড়
  [[1, 1], true],
  [[1], false],                               // single, বিজোড়
  [[2, 2, 2, 2], true],
  [[100], false],
  [[3, 3, 3, 4, 5], true],                    // target 9: 4+5 বা 3+3+3
  [[1, 2, 5], false],                         // সম-মোট কিন্তু unreachable
];
for (const [nums, want] of cases) {
  assert(canPartition(nums) === want, "part " + nums);
}
console.log("সব JS test pass!");

JS টীকা: 0/1 নিশ্চিত করতে inner loop s = target থেকে x পর্যন্ত নিচে (s--) — বাঁ-থেকে-ডান করলে একই item বহুবার গোনা হয়ে ভুল true আসতে পারে। মোট sum বের করতে nums.reduce((a,b)=>a+b, 0) (initial value 0 দাও, খালি array-তে নিরাপদ)। new Array(n).fill(false) boolean primitive বলে নিরাপদ; বিজোড় sum আগে check করলে target integer থাকে।

TypeScript ও test cases¶

TypeScript

function canPartition(nums: number[]): boolean {
  const total: number = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target: number = total / 2;
  const dp: boolean[] = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      if (dp[s - x]) dp[s] = true;
    }
  }
  return dp[target];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number[], boolean]> = [
  [[1, 5, 11, 5], true],
  [[1, 2, 3, 5], false],
  [[1, 1], true],
  [[1], false],
  [[2, 2, 2, 2], true],
  [[3, 3, 3, 4, 5], true],
  [[1, 2, 5], false],
];
for (const [nums, want] of cases) expect(canPartition(nums), want, "part");
console.log("সব TS test pass!");

TS টীকা: dp: boolean[] typing দিয়ে DP array যে boolean-এর (number নয়) তা locked — ভুলে সংখ্যা মেশানো compile-error; return type boolean ফাংশনের হ্যাঁ/না প্রকৃতি স্পষ্ট করে। cases: Array<[number[], boolean]> tuple-type input/expected জোড়া নিশ্চিত করে।

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

সময়¶

দুই version-ই O(n × target) (pseudo-polynomial) — n item, প্রতিটায় target পর্যন্ত sum। target ≈ মোট sum-এর অর্ধেক।

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

Memoization: O(n × target) — dict + recursion stack।
Tabulation: O(target) — 1D boolean array।

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

Inner loop বাঁ-থেকে-ডান করা — তখন একই item বহুবার গোনা হয় (unbounded), ভুল True আসতে পারে; 0/1-এর জন্য অবশ্যই ডান-থেকে-বাঁ।
বিজোড় মোট sum আগে check না করা — target তখন float/ভুল integer হয়, বা অযথা কাজ।
subset-sum-কে "দুই array ভাগ" হিসেবে জটিল করা — এক subset total/2 পেলেই যথেষ্ট, বাকিটা এমনিই।

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

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

ভিত্তি: 0/1 knapsack skeleton — value-র জায়গায় boolean reachability। ../state-transition-thinking.md-এর "Problem 6 — 0/1 Knapsack" section-এ ঠিক এই take-or-leave state আর loop-direction warning আছে; ../patterns.md-এর "Subset-sum / 0/1 knapsack" family-ও এখানে।

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

Book Shop (0/1 knapsack, value maximize) — https://cses.fi/problemset/task/1158 (এই tracker-এর #14)
Target Sum (+/- চিহ্ন বসিয়ে target, subset-sum-এ রূপান্তর) — https://leetcode.com/problems/target-sum/
Last Stone Weight II (দুই ভাগের পার্থক্য minimize) — https://leetcode.com/problems/last-stone-weight-ii/

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

Subset-sum (0/1 boolean): state "sum s reachable কি না," transition dp[s] = dp[s] or dp[s-x], base dp[0]=True, inner loop right-to-left (0/1)। "দুই-ভাগ সমান" = "একটা subset = অর্ধেক sum" — reduction-টা মনে রাখার মতো। 0/1 vs unbounded শুধু loop direction-এ আলাদা।

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

ভবিষ্যতের আমাকে: "Partition Equal Subset Sum = subset-sum reachability total/2।" State dp[s] = sum s reachable, transition dp[s] = dp[s] or dp[s-x], base dp[0]=True, উত্তর dp[total/2] (মোট বিজোড় হলে False)। মনে রেখো: 0/1 নিশ্চিত করতে inner loop ডান-থেকে-বাঁ।

কোথায় কাজে লাগে¶

Fair division / load balancing: একগুচ্ছ কাজ/ওজনকে দুই সমান অংশে ভাগ করা যায় কিনা (দুই machine/worker-এ সমান load)।
Resource splitting: দুই দল/পার্টিশনে সমান মোট মান বণ্টন সম্ভব কিনা যাচাই।
Set / bin balancing: দুই bin-এ আইটেম এমনভাবে ভাগ যেন যোগফল সমান (scheduling, packing)।
Subset reachability check: নির্দিষ্ট target যোগফল কোনো subset দিয়ে পাওয়া যায় কিনা (budget/quota feasibility)।
Cryptography / number theory toy: subset-sum-ভিত্তিক feasibility (NP-hard-এর pseudo-polynomial রূপ)।

মূল pattern: "দুই-ভাগ সমান" = "একটা subset = অর্ধেক sum"; dp[s] = dp[s] or dp[s-x], inner loop right-to-left (0/1)।

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