পাইথনে লিস্টকে দুটি সমান সম হয় এমন প্যার্টিশনে ভাগ করা সম্ভব কিনা চেক করা

সমস্যা বিবরণ

একটি সংখ্যা লিস্ট nums দেওয়া আছে। এটি কি দুটি গ্রুপে ভাগ করা সম্ভব যাতে দুটি গ্রুপের যোগফল সমান হয়? (Partition Equal Subset Sum)

উদাহরণ

Input:  nums = [2, 3, 6, 5]
Output: True
ব্যাখ্যা: Group 1: [2, 6] = 8, Group 2: [3, 5] = 8

কী অভিজ্ঞতা

• টোটাল সম যদি বিজোড় হয় → অসম্ভব
• টোটাল সম = S, তাহলে প্রতিটি গ্রুপের সম = S/2
• সমস্যা: সাবসেট সম = S/2 এমন সাবসেট আছে কিনা? (Subset Sum Problem)

অ্যালগরিদম: Dynamic Programming

1. total = sum(nums), বিজোড় হলে False
2. target = total // 2
3. dp[i] = যোগফল i বানানো সম্ভব কিনা (Boolean)
4. dp[0] = True
5. প্রতিটি num এর জন্য target থেকে ০ পর্যন্ত পিছিয়ে যান:
   • dp[i] = dp[i] or dp[i - num]
6. dp[target] রিটার্ন করুন

পাইথন কোড

class Solution:
    def solve(self, nums):
        total = sum(nums)
        if total & 1:  # বিজোড় চেক
            return False
        
        target = total // 2
        dp = [True] + [False] * target  # dp[0] = True
        
        for num in nums:
            for i in range(target, 0, -1):  # রিভার্স: একবার ইউজ
                if i >= num:
                    dp[i] |= dp[i - num]
        
        return dp[target]

ob = Solution()
nums = [2, 3, 6, 5]
print(ob.solve(nums))  # True

কেন রিভার্স লুপ?

for i in range(target, 0, -1) — একই ইটারেশনে একই নাম্বার একাধিকবার ইউজ হয় না। ফরোয়ার্ড লুপ দিলে আনলিমিটেড নাপস্যাক (Unbounded Knapsack) হয়ে যায়।

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n × target) — n = লিস্ট সাইজ
• স্থান জটিলতা: O(target) — ১D DP অ্যারে
• Pseudo-polynomial: target বড় হলে স্লো

অপ্টিমাইজেশন: বিটসেট (Bitwise)

def solve_bitset(nums):
    total = sum(nums)
    if total & 1: return False
    target = total // 2
    bits = 1  # bit 0 = True
    for num in nums:
        bits |= (bits << num)
    return (bits >> target) & 1 == 1

বিটওয়াইজ অপারেশন দিয়ে ৬৪গুণ দ্রুত (Python-এ বড় ইন্ট সাপোর্ট করে)।

উপসংহার

• Subset Sum = Partition Equal Subset Sum
• DP বা বিটসেট ব্যবহার করুন
• বড় target এর জন্য Meet-in-the-Middle বা Approximation Алгоритম