思路和算法
如果可以将数组分割成两个元素和相等的子集，则必须同时满足两个条件：第一个条件是数组元素和是偶数，第二个条件是数组的最大元素不能超过数组元素和的一半。
如果第一个条件不满足，则数组元素和是奇数，奇数不可能分成两个相等的整数之和，因此不可能将数组分割成两个元素和相等的子集。
如果第二个条件不满足，则数组的最大元素大于数组的其余元素之和，由于数组的最大元素一定在其中一个子集，因此数组的最大元素所在子集的元素和一定大于另一个子集的元素和，不可能将数组分割成两个元素和相等的子集。
以下只考虑同时满足上述两个条件的情况。
用 n 表示数组 nums 的长度，用 sum 表示数组 nums 的元素和，用 target= sum/2
表示数组 nums 的元素和的一半。需要判断是否可以从数组 nums 中选取一个或多个数，满足选取的数之和等于 target。
该问题是 0-1 背包问题的变种，和传统 0-1 背包问题的区别在于，这道题要求选取的元素之和恰好等于 target。对于每个元素，选取的元素之和取决于之前选取的元素，因此可以使用动态规划判断是否可以将数组分割成两个元素和相等的子集。
创建 (n+1)×(target+1) 的二维数组 dp，其中 dp[i][j] 表示在前 i 个元素中选取元素是否可以使元素和等于 j。
当 i=0 时，没有任何元素，元素和一定是 0，因此动态规划的边界情况是：当 j=0 时 dp[0][j]=true，当 j>0 时 dp[0][j]=false。
当 i>0 时，当前元素是 nums[i−1]，只有当 j≥nums[i−1] 时才能选取当前元素。分别考虑 j<nums[i−1] 和 j≥nums[i−1] 的情况。
如果 j<nums[i−1]，则不能选取当前元素，在前 i 个元素中选取元素使元素和等于 j 等价于在前 i−1 个元素中选取元素使元素和等于 j，因此可行性为 dp[i−1][j]。
如果 j≥nums[i−1]，则可以不选取或选取当前元素，根据两种情况判断可行性。
如果不选取当前元素，则需要在前 i−1 个元素中选取元素使元素和等于 j，可行性为 dp[i−1][j]。
如果选取当前元素，则需要在前 i−1 个元素中选取元素使元素和等于 j−nums[i−1]，加上选取的当前元素之后元素和等于 j，因此可行性为 dp[i−1][j−nums[i−1]]。
因此动态规划的状态转移方程如下。
如果 j<nums[i−1]，则 dp[i][j]=dp[i−1][j]。
如果 j≥nums[i−1]，则当 dp[i−1][j]=true 或 dp[i−1][j−nums[i−1]] 时 dp[i][j]=true，否则 dp[i][j]=false。
根据动态规划的状态转移方程，计算 dp[i][j] 的顺序为从小到大遍历每个 i。计算得到 dp[n][target] 即为答案。
上述做法的时间复杂度和空间复杂度都是 O(n×sum)。
实现方面可以优化空间，做法如下。
由于 dp[i][] 只取决于 dp[i−1][]，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一个 i 处的状态，将空间复杂度降到 O(sum)。
优化空间时，如果从小到大遍历每个 j 则对于每个遍历到的 i 都需要新建一个临时数组。可以进一步优化空间，从大到小遍历每个 j，则不需要新建临时数组。
参考storm大神
class Solution { public boolean canPartition(int[] nums) { int sum = 0, maxNum = 0; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 != 0 || maxNum * 2 > sum) { return false; } int n = nums.length; int target = sum / 2; boolean[][] dp = new boolean[n + 1][target + 1]; dp[0][0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j <= target; j++) { if (j < nums[i - 1]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]; } } } return dp[n][target]; } }