LeetCode刷题：416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
题目大意是：给定一个仅包含正整数的非空数组，查找该数组是否可以划分为两个子集，以便两个子集中的元素之和相等。
算法设计
class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int item : nums){sum += item;}//如果数组元素和不是2的倍数，直接返回falseif (sum % 2 != 0)return false;return knapSack(nums,sum/2);}private boolean knapSack(int[] nums,int sum){int size = nums.length;boolean[] dp = new boolean[sum + 1];for (int i = 0;i <= sum;i ++){dp[i] = i == nums[0];}for (int i = 1;i < size;i++){for (int j = sum;j >= nums[i];j--){dp[j] = dp[j] || dp[j-nums[i]];}}return dp[sum];}}LeetCode上提交，AC的结果
