題目：

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.
Example1：

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

Example2：

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

思路：

該題采用動(dòng)態(tài)規(guī)劃的思路來做。

• dp[i][n] : 代表i個(gè)物品在體積為n的情況下的最大值。
• 狀態(tài)轉(zhuǎn)移方程:

dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[]i);

注意：
數(shù)組中所有數(shù)的和必須為偶數(shù)。如果為奇數(shù)則返回false。是偶數(shù)則和sum除以2。求出n個(gè)物品在體積為sum/2的情況下的最大值。

如果dp[n][sum/2] == sum/2返回True，否則返回False。

代碼：

public boolean canPartition(int[] nums) {
        boolean flag = false;
        if(nums == null || nums.length == 0)
            return flag;
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(sum % 2 == 1)
            return false;
        sum /= 2;
        int [][] dp = new int [nums.length][sum + 1];
        for(int i=nums[0];i<sum+1;i++){
            dp[0][i] = nums[0];
        }
        for(int i=1;i<nums.length;i++){
            for(int j=nums[i];j<sum+1;j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
            }
        }
        return dp[nums.length - 1][sum] == sum ? true : false;
}