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:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets. 题目含义：多个正数组成的数组，能否分成两个子数组，使得两个子数组的和相等

1     public boolean canPartition(int[] nums) { 2         int sum=0; 3         for (int num:nums) sum+= num; 4         if(sum % 2 == 1) return false; 5         sum /=2; 6         boolean[] dp = new boolean[sum + 1];//当前可以由考虑了的元素构成的值（每个元素最多出现1次） 7         //0可以由给定的nuns数组的元素组成给出 8         dp[0] = true; 9         int curSum = 0;10         //nums中的元素可以划分为2类：考虑了的和没考虑了的11         for (int num: nums) {
   //一个一个元素按顺序加入考虑了的划分中，从而考虑全部可以构成的数的值12             int tmax = Math.min(curSum + num, sum);//内循环的上限的有效值=min（当前考虑了的划分中的元素可以构成的最大的值，sum）13             for (int j = tmax; j >= num; j--) {14                 //构成j值只有2种情况：包含num，不包含num15                 //包含nums[i]：dp[j] = dp[j - num]16                 //不包含nums[i]：dp[j] = dp[j]17                 dp[j] = dp[j] || dp[j - num];18             }19             if (dp[sum]) return true;//一旦满足直接返回，减少遍历20             curSum += nums[i];21         }22         return dp[sum]; 23     }