416. 分割等和子集

问题分析：除了直接利用01背包的思想来做（即从nums[] 中寻找元素，判断其元素和是否等于 nums[]所有元素的一半），我们还通过微调dp方程的定义，直接得到转移状态。
状态定义：dp[i][j]表示考虑前 i 个数字，是否可以恰好填充满背包容量为 j 的背包。
状态初始化：我们对状态方程的定义做了下标偏移，所以对于i=0的情况，我们可以这样理解，在不考虑任何数字的前提下，填充满容量为0的背包是完全有可能的，其他情况均为不可能，
即：dp[0][0]=true, dp[0][1, ...]=false。
状态转移：dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]] if j >=nums[i-1]。

解法一（最朴素）

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 2 != 0){ //如果nums中元素总和为奇数，那么不可能划分为两个总和相当的子集
            return false;
        }
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][sum / 2 + 1];
        dp[0][0] = true;
        for(int i = 1; i <= n; i++){
            int val = nums[i - 1];
            for(int j = 0; j <= sum / 2; j++){
                boolean a = dp[i-1][j];
                boolean b = j - val >= 0 ? dp[i - 1][j - val] : false;
                dp[i][j] = a || b;
            }
        }
        return dp[n][sum / 2];
    }
}

解法二（一维）

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 2 != 0){
            return false;
        }
        int n = nums.length;
        boolean[] dp = new boolean[sum / 2 + 1];
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            int val = nums[i - 1];
            for(int j = sum / 2; j >= val; j--){
                dp[j] |= dp[j - val];
            }
        }
        return dp[sum / 2];
    }
}