416. Partition Equal Subset Sum 发表于 2022-01-23 DFS1234567891011121314151617181920212223242526272829303132333435class Solution { public boolean canPartition(int[] nums) { int sum = Arrays.stream(nums).sum(); if ((sum & 1) == 1) { return false; } Set<Integer> memo = new HashSet<>(); int targetSum = sum >> 1; return dfs(nums, 0, 0, targetSum, memo); } private boolean dfs(int[] nums, int startIndex, int currentSum, int targetSum, Set<Integer> memo) { if (memo.contains(currentSum * 201 + startIndex)) { return false; } if (currentSum == targetSum) { return true; } if (startIndex < nums.length && currentSum < targetSum) { // choose if (dfs(nums, startIndex + 1, currentSum + nums[startIndex], targetSum, memo)) { return true; } // not choose if (dfs(nums, startIndex + 1, currentSum, targetSum, memo)) { return true; } } memo.add(currentSum * 201 + startIndex); return false; }} DP123456789101112131415161718192021222324252627282930313233class Solution { public boolean canPartition(int[] nums) { int sum = 0; int maxNum = Integer.MIN_VALUE; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } int targetSum = sum >> 1; if ((sum & 1) == 1 || maxNum > targetSum) { return false; } // 定义 dp[i][j] 从 nums 前 i 个元素中任意选择一些元素是否能组成和 j // dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[0...i - 1]] boolean[][] dp = new boolean[nums.length + 1][targetSum + 1]; for (int i = 0; i <= nums.length; i++) { dp[i][0] = true; // 从前 i 个元素中选择 0 个元素时都能组成和 0 } for (int i = 1; i <= nums.length; i++) { for (int j = 1; j <= targetSum; j++) { dp[i][j] = dp[i - 1][j]; // 不选择当前元素 if (!dp[i][j] && j - nums[i - 1] >= 0) { dp[i][j] |= dp[i - 1][j - nums[i - 1]]; } } } return dp[nums.length][targetSum]; }} DP1234567891011121314151617181920212223242526272829303132class Solution { public boolean canPartition(int[] nums) { if (nums.length < 2) { return false; } int maxNum = Integer.MIN_VALUE; int sum = 0; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } int targetSum = sum >> 1; if ((sum & 1) == 1 || maxNum > targetSum) { return false; } boolean[] dp = new boolean[targetSum + 1]; dp[0] = dp[nums[0]] = true; for (int i = 1; i < nums.length; i++) { for (int j = targetSum; j >= 1; j--) { // 注意此处倒序,因为 dp[j] depends on dp[j - nums[i]], 为了防止状态被覆盖 if (j - nums[i] >= 0) { dp[j] = dp[j] | dp[j - nums[i]]; } } } return dp[targetSum]; }} Reference416. Partition Equal Subset Sum