Level：
Medium
题目描述：
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.
思路分析：
方法一：利用暴力的dfs进行遍历，找数组中有么有和为sum/2的组合，先看sum是否为偶数，如果为奇数直接false。
方法二：动态规划的思想。我们定义一个一维的dp数组，其中dp[i]表示原数组是否可以取出若干个数字，其和为i。那么我们最后只需要返回dp[target]就行了。初始化dp[0]为true，由于题目中限制了所有数字为正数，那么就不用担心会出现和为0或者负数的情况。关键问题就是要找出状态转移方程了，我们需要遍历原数组中的数字，对于遍历到的每个数字nums[i]，需要更新dp数组，我们的最终目标是想知道dp[target]的boolean值，就要想办法用数组中的数字去凑出target，因为都是正数，所以只会越加越大，那么加上nums[i]就有可能会组成区间 [nums[i], target] 中的某个值，那么对于这个区间中的任意一个数字j，如果 dp[j - nums[i]] 为true的话，说明现在已经可以组成 j-nums[i] 这个数字了，再加上nums[i]，就可以组成数字j了，那么dp[j]就一定为true。如果之前dp[j]已经为true了，当然还要保持true，所以还要‘或’上自身，于是状态转移方程如下：
dp[j] = dp[j] || dp[j - nums[i]] (nums[i] <= j <= target)
有了状态转移方程，那么我们就可以写出代码了，这里需要特别注意的是，第二个for循环一定要从target遍历到nums[i]，而不能反过来，想想为什么呢？因为如果我们从nums[i]遍历到target的话，假如nums[i]=1的话，那么[1, target]中所有的dp值都是true，因为dp[0]是true，dp[1]会或上dp[0]，为true，dp[2]会或上dp[1]，为true，依此类推，完全使我们的dp数组失效了。
代码：
思路一：
public class Solution{
public boolean canPartition(int []nums){
int sum=0;
for(int i=0;i<nums.length;i++){
sum=sum+nums[i];
}
if(sum%2==1)
return false;
sum=sum/2;
Arrays.sort(nums);//排序，方剪枝
return dfs(0,sum,nums);
}
public boolean dfs(int index,int sum,int []nums){
if(index<nums.length&&nums[index]==sum)
return true;
if(index<nums.length&&nums[index]>sum)
return false;
return dfs(index+1,sum-nums[index],nums)||dfs(index+1,sum,nums);
}
}
思路二：
public class Solution{
public boolean canPartition(int []nums){
int sum=0;
for(int i=0;i<nums.length;i++){
sum=sum+nums[i];
}
if(sum%2==1)
return false;
sum=sum/2;
boolean []dp=new boolean[sum+1];//dp[i]表示和为i能否由数组中部分元素构成
Arrays.fill(dp,false);
dp[0]=true;
for(int num:nums){
for(int i=sum;i>=num;i--){
dp[i]=dp[i]||dp[i-num];
}
}
return dp[sum];
}
}