Cho list nums, kiểm tra có thể phân hoạch thành 2 nhóm bằng tổng không (Partition Problem).
Ví dụ: nums = [2, 3, 6, 5] → True (nhóm [2,6] và [3,5] đều tổng 8).
Giải pháp: Quy hoạch động 0/1 knapsack. Nếu tổng lẻ → False. Target = tổng/2. dp[i] = có thể tạo tổng i không. Duyệt từng số, cập nhật dp từ target về 0.
Ví dụ triển khai
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
Đầu vào
[2, 3, 6, 5]
Đầu ra
True