image.png
问题分析：此问题为什么可以利用01背包求解？我们假设nums[] 所有元素的总和为sum，那么我们把问题转化为，给定一系列物品，其中每样物品的价值和重量相等，即为nums[i]，且背包容量为 sum / 2，求当前背包容量下的最大价值。

解法一（最朴素）

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int sum = 0;
  4.         for(int num : nums){
  5.             sum += num;
  6.         }
  7.         if(sum % 2 != 0){
  8.             return false;
  9.         }
  11.         int n = nums.length;
  12.         int[][] dp = new int[n + 1][sum / 2 + 1];
  13.         for(int i = 1; i <= n; i++){
  14.             int val = nums[i - 1];
  15.             for(int j = 0; j <= sum / 2; j++){
  16.                 int a = dp[i - 1][j];
  17.                 int b = j - val >= 0 ? dp[i -1][j - val] + val : 0;
  18.                 dp[i][j] = Math.max(a, b);
  19.             }
  20.         }
  21.         return dp[n][sum / 2] == sum / 2;
  22.     }
  23. }

解法二（一维解法）

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int sum = 0;
  4.         for(int num : nums){
  5.             sum += num;
  6.         }
  7.         if(sum % 2 != 0){
  8.             return false;
  9.         }
  11.         int n = nums.length;
  12.         int[] dp = new int[sum / 2 + 1];
  13.         for(int i = 1; i <= n; i++){
  14.             int val = nums[i - 1];
  15.             for(int j = sum / 2; j >= val; j--){
  16.                 dp[j] = Math.max(dp[j], dp[j -val] + val);
  17.             }
  18.         }
  19.         return dp[sum / 2] == sum / 2;
  20.     }