ตรวจสอบแบ่งลิสต์เป็น 2 กลุ่มมีผลรวมเท่ากันได้หรือไม่ใน Python

Partition Problem: แบ่งลิสต์ nums เป็น 2 กลุ่ม ผลรวมเท่ากัน

ตัวอย่าง: nums = [2, 3, 6, 5] → True (กลุ่ม [2,6] และ [3,5] ผลรวม 8)

แนวทาง (Dynamic Programming - Subset Sum)

1. ถ้า sum(nums) เป็นคี่ → False
2. หา half = sum // 2
3. DP: dp[i] = สามารถทำผลรวม i ได้หรือไม่
4. เริ่ม dp[0] = True
5. สำหรับแต่ละ num อัปเดต dp จากหลังมาหน้า

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums):
        total = sum(nums)
        if total & 1:
            return False
        half = total // 2
        dp = [True] + [False] * half
        for num in nums:
            for i in range(half, 0, -1):
                if i >= num:
                    dp[i] |= dp[i - num]
        return dp[half]

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

อินพุต

[2, 3, 6, 5]

เอาต์พุต

True