416. 分割等和子集 - 力扣（LeetCode）
首先先求数组中所有的数之和，如果不能被2整除，那就不能分割两个子集元素和相等。r然后直接套用01背包模版即可。
背包的容量即为所有数之和在除2，如果dp最后一个元素与背包的容量相等，那么即为可以分割成两个相等的子集。
public class Q416 {public static void main(String[] args) {int[] nums = {1,2,3,5};System.out.println(canPartition(nums));}public static boolean canPartition(int[] nums) {int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}if (sum % 2 != 0) return false;int m = nums.length;int n = sum / 2;int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (nums[i-1] > j) {//如果放不下当前元素dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);}//System.out.print(dp[i][j] + " ");}//System.out.println();}return dp[m][n] == n;}
}
)
