Can Partition to Equal Sum Subsets
easy
Given an array of positive integers, determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example 1
Input
[ 1, 5, 11, 5 ]
Output
true
Explanation. The array can be partitioned as [1, 5, 5] and [11] which both sum to 11.
Example 2
Input
[ 1, 2, 3, 5 ]
Output
false
Explanation. It is not possible to partition this array into two subsets with equal sums.
Example 3
Input
[ 3, 3, 3, 3, 4 ]
Output
true
Explanation. The array can be partitioned as [3, 3, 4] and [3, 3] which both sum to 10.
Example 4
Input
[ 1, 1 ]
Output
true
Explanation. The array can be partitioned into two subsets [1] and [1], each summing to 1.
Follow-up: Could there be a solution that optimizes the space complexity beyond simply using an additional array to track subset sums?
Constraints:
All numbers in the input array are positive integers. The length of the array will be at least 2.