解法一：动态规划 二维01背包

首先求和判断是否为偶数，如果和为奇数的话必不可能分成两个等和子集。然后对和除以2，得到的就是每个子集的元素之和 sum ，接下来就是一个类似01背包的问题。
记 dp[i][j] 表示在前 i 个数（数的索引从1开始）中任取，是否存在和为 j 的方案，存在则为 true ，不存在则为 false 。状态转移方程如下：
416. 分割等和子集 - 图1

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {i]
  3.         int sum = 0;
  4.         for (int i : nums) {
  5.             sum += i;
  6.         }
  7.         if ((sum & 1) == 1) {
  8.             return false;
  9.         }
  10.         sum /= 2;
  11.         final int n = nums.length;
  12.         boolean[][] dp = new boolean[n + 1][sum + 1];
  13.         dp[0][0] = true;
  14.         for (int i = 0; i < n; ++i) {
  15.             for (int j = 1; j <= sum; ++j) {
  16.                 dp[i + 1][j] = dp[i][j];
  17.                 if (j >= nums[i]) {
  18.                     dp[i + 1][j] = dp[i + 1][j] || dp[i][j - nums[i]];
  19.                 }
  20.             }
  21.         }
  22.         return dp[n][sum];
  23.     }
  24. }

解法二：动态规划 一维01背包

注意到在解法一中， dp[i][:] 的状态仅和 dp[i-1][:] 相关，因此可以改写成一维的形式，但是要注意遍历的顺序要反转，防止提前覆盖前一轮的结果。

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int sum = 0;
  4.         for (int i : nums) {
  5.             sum += i;
  6.         }
  7.         if ((sum & 1) == 1) {
  8.             return false;
  9.         }
  10.         sum /= 2;
  11.         final int n = nums.length;
  12.         boolean[] dp = new boolean[sum + 1];
  13.         dp[0] = true;
  14.         for (int i = 0; i < n; ++i) {
  15.             for (int j = sum; j >= 1; --j) {
  16.                 if (j >= nums[i]) {
  17.                     dp[j] = dp[j] || dp[j - nums[i]];
  18.                 }
  19.             }
  20.         }
  21.         return dp[sum];
  22.     }
  23. }