给你一个 只包罗正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相称。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相称的子集。
提示：
1 <= nums.length <= 200
1 <= nums <= 100
java代码：
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) { return false; } int sum = 0, maxNum = 0; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 != 0) { return false; } int target = sum / 2; if (maxNum > target) { return false; } boolean[][] dp = new boolean[n][target + 1]; for (int i = 0; i < n; i++) { dp[0] = true; } dp[0][nums[0]] = true; for (int i = 1; i < n; i++) { int num = nums; for (int j = 1; j <= target; j++) { if (j >= num) { dp[j] = dp[i - 1][j] | dp[i - 1][j - num]; } else { dp[j] = dp[i - 1][j]; } } } return dp[n - 1][target]; }} |
