Partition Equal Subset Sum
Reformulate the partition problem as a 0/1 knapsack on a target of total-sum/2, detecting feasibility with a boolean DP array.
Problem Statement
Given a non-empty array of positive integers nums, determine if you can partition it into two subsets with equal sum. For example, [1, 5, 11, 5] can be partitioned into [1, 5, 5] and [11], both summing to 11. If the total sum is odd, the answer is immediately False. Otherwise, we need to find a subset summing to total_sum // 2 — a classic subset sum problem.
Reduction to Subset Sum
The key reduction: if total sum S is even and a subset sums to S//2, the remaining elements automatically sum to S//2 as well. So Partition Equal Subset Sum reduces to: does any subset of nums sum to S//2? This is the classic NP-complete Subset Sum problem, which we solve with 0/1 knapsack DP in O(n × S) time.
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?