def partition_problem(nums, n):
def knapsack(nums, n, total):
dp = [0] * (total + 1)
for i in range(n):
for j in range(total, nums[i] - 1, -1):
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
return dp[total]
total = sum(nums)
if total % 2 != 0:
return False
total //= 2
return knapsack(nums, n, total) == total
nums = [1, 5, 11, 5]
n = len(nums)
if partition_problem(nums, n):
print("Can be divided into two subsets of equal sum")
else:
print("Can't be divided into two subsets of equal sum")