题目：分割等和子集

  • 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
  • 每个数组中的元素不会超过 100
  • 数组的大小不会超过 200
示例 1:
  1. 输入: [1, 5, 11, 5]
  2. 输出: true
  3. 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例2:
  1. 输入: [1, 2, 3, 5]
  2. 输出: false
  3. 解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）第416题

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

分析：

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

代码：

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