Partition Equal Subset Sum

Given an array of positive integers, print true if it can be split into two subsets with equal sum, false otherwise.

Example

Input: 1 5 11 5 Output: true ([1, 5, 5] and [11] both sum to 11)

Approach

If the total sum is odd, it's immediately impossible. Otherwise this reduces to the classic 0/1 knapsack question: "can some subset sum to exactly total / 2?" — a boolean DP array over achievable sums, each number used at most once, iterated in descending sum order to avoid reusing an item within the same pass.

Input format

Line 1: the array, space-separated

Print true or false.