题目：分割等和子集

• 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

• 每个数组中的元素不会超过 100
• 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）第416题

链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

分析：

• 动态规划题
• 0-1背包问题

代码：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int len = nums.length;
        for (int num : nums) sum += num;
        if ((sum & 1) == 1) return false; // 如果是奇数，不可能分割
        sum >>= 1; // 要找的答案是总和的一半。
        boolean[][] dp = new boolean[len][sum+1]; // i表示nums中从0到i为止，j表示是否能找到和为j的数。
        if (nums[0] <= sum) dp[0][nums[0]] = true; // 第一个数放在j上，其他都是false
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= sum; j++) {
                if (nums[i] <= j) 
                // 两种选择，一种之前就找到了和为j的数，那么现在还是true。
                // 如果之前没有找到和为j的数，那么我加上这次的数，要找前一次j-nums[i]的和能不能找到。
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                else // 如果当前nums[i] 大于j的话，之前看它前一次是什么状态现在还是什么状态。
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[len-1][sum];
    }
}