共计 1166 个字符，预计需要花费 3 分钟才能阅读完成。
题目要求
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: 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.
假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。
思路和代码
这和 0 - 1 背包问题是完全一样的，01 背包问题是指假设有 n 个物品，每个物品中为 weight[i]，假设背包的承重为 k，问如何选择物品使得背包中的承重最大。而这里的问题等价于，有 n 个物品，每个物品承重为 input[i]，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。
假设我们已经知道前 i 个物品是否能够构成重量 k，我们令该值为 dpi，那么第 i + 1 个物品是否能够构成重量取决于 dpi 和 dpi], 即 i + 1 个物品能够构成重量 k 有两种情况，第一种选择了 i + 1 个物品，则要寻找前 i 个物品是否构成 k -input[i+1] 的重量，第二种就是没有选择第 i + 1 个物品，则直接判断前 i 个物品是否已经构成了 k 的重量。
代码如下：
public boolean canParition(int[] nums) {
int sum = 0;
for(int n : nums) {
sum += n;
}
if(sum % 2 != 0) return false;
int half = sum / 2;
boolean[][] sums = new boolean[nums.length+1][half+1];
for(int i = 0 ; i<=nums.length ; i++) {
for(int j = 0 ; j<=half ; j++) {
if(i==0 && j==0){
sums[i][j] = true;
}else if(i==0) {
sums[i][j] = false;
}else if(j==0){
sums[i][j] = true;
}else {
sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false);
}
}
}
return sums[nums.length][half];
}
