This is the PARTITION problem:
Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets.
This is the SUBSET SUM problem:
Given a multiset S of integers and an integer T, decide if any subset of S sums to T.
The positive variant of SUBSET SUM is NP-complete.
SUBSET SUM can be reduced to PARTITION as follows:
Define S' = S + {c}, where c = 2T - sum(S). S' can be partitioned into two equal-sum subsets iff there is a subset in S summing to T.
Proof:
Partition S into A and B:
S = A + B
If there exists a subset in S summing to T, then S can be partitioned so either sum(A) = T or sum(B) = T. Suppose sum(A) = T. Let S' = A + B' where B' = B + {c}.
sum(B') = sum(S) - sum(A) + c sum(B') = sum(S) - sum(A) + 2T - sum(S) sum(B') = -sum(A) + 2T By assumption, T = sum(A) therefore sum(B') = sum(A). This means S' can be partitioned into two equal-sum subsets.
If there does not exist a subset in S summing to T, then there cannot exist a c such that S' can be partitioned into two equal-sum subsets.
Suppose for contradiction c can exist.
Adding c to B creates S' = A + B'.
What value of T produces c such that sum(A) = sum(B') = sum(B) + c?
sum(A) = sum(B) + c sum(A) = sum(B) + 2T - sum(S) sum(A) = sum(B) + 2T - (sum(A) + sum(B)) sum(A) = sum(B) + 2T - sum(A) - sum(B) 2sum(A) = 2T sum(A) = T But A already sums to sum(A), contradicting the assumption that there is no subset of S summing to T.
If 2T < sum(S), then c < 0, but PARTITION only applies for positive integer multisets. Does this reduction still hold?
