难度中等421
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100数组的大小不会超过 200示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. //先计算总和 如何是奇数说明不可能进行分隔，直接返回false //dp 1.找到重复子问题 2.dp状态定义与选择 3.dp方程 //对于每个数只能选举一次，所以 只需要进行一次遍历 //w 是最大值 public boolean canPartition(int[] nums) { int sum = computeArraySum(nums); if (sum % 2 != 0) { return false; } int w = sum/2; boolean [] dp = new boolean[w+1]; dp[0] = true; for (int num : nums) { for (int i=w; i>=num ;i--) { dp[i] = dp[i] || dp[i-num]; } } return dp[w]; } private int computeArraySum(int [] nums) { int sum = 0; for (int num :nums) { sum+=num; } return sum; }