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:

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.

class Solution {
    public boolean canPartition(int[] nums) {
        int le = nums.length;
        int cur = 0;
        for(int i: nums) cur += i;
        if((cur & 1) == 1) return false;
        boolean[][] dp = new boolean[le+1][cur/2+1];
        dp[0][0] = true;
        for(int i = 0; i < le+1; i++) dp[i][0] = true;
        for(int i = 1; i < le+1; i++){
            for(int j = 1; j < cur/2 + 1; j++){
                dp[i][j] = dp[i-1][j];
                if(nums[i-1] <= j) dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
            }
        }
        return dp[le][cur/2];
    }
}

一个很好的背包问题，要两个subset相等，那就说明一个subset的和是sum/2.

然后有dp数组 dp[ length+1] [ sum/2 + 1]。dp数组dp[i][j]意思是有i个nums，能从中形成一个subset使和等于j，首先初始化dp，dp【i】【0】== true，因为sum == 0时无论是什么subset都可以（空集）

同时注意，nums[ i - 1 ] <= j时才需要更新，因为当前value要小于等于背包的大小。

dp【i】【j】 = dp【i-1】【j】（不选nums【i】） || dp【i - 1】【j - nums【 i - 1】（选nums【i - 1】）

最后返回dp的右下角