leetcode 416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note: Each of the array element will not exceed 100. The array size will not exceed 200. Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2: Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

首先将所有元素相加，若为奇数直接返回false，为偶数，除以2得到需要组合得到的加和。目的就是从原始数组中找到这样一个组合。这就是一个背包问题 暴力解法，对于每个元素有加与不加两种选择，递归的调用，这样照成的复杂度为 O(2N) 。暴力解法如下：

boolean isValid(int[] nums, int target, int i){ if(i==nums.length) return false; if(nums[i]==target) return true; return isValid(nums, target - nums[i], i+1) || isValid(nums, target, i+1); }

采用动态规划的方法 d[i][j] 表示用数组的前i个元素能否组成j 如果不选第i个元素，那么 d[i][j]=d[i−1][j] ，否则 d[i][j]=d[i−1][j−nums[i]] ，即前i-1个元素能否组成 j−nums[i] ，这样解法为

public boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) { sum += num; } if ((sum & 1) == 1) { return false; } sum /= 2; int n = nums.length; boolean[][] dp = new boolean[n+1][sum+1]; for (int i = 0; i < dp.length; i++) { Arrays.fill(dp[i], false); } dp[0][0] = true; for (int i = 1; i < n+1; i++) { dp[i][0] = true; } for (int j = 1; j < sum+1; j++) { dp[0][j] = false; } for (int i = 1; i < n+1; i++) { for (int j = 1; j < sum+1; j++) { dp[i][j] = dp[i-1][j]; if (j >= nums[i-1]) { dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]); } } } return dp[n][sum]; }

采用空间压缩的方法可以让dp降为一维

public boolean canPartition(int[] nums) { int sum = 0; for(int i=0; i < nums.length; i++){ sum += nums[i]; } if(sum%2==1) return false; sum /=2; // return isValid(nums, sum_all, 0); boolean[] dp = new boolean[sum+1]; dp[0] = true; for(int i=0; i< nums.length; i++){ for(int j=sum; j>=nums[i]; j--){ dp[j] = dp[j] || dp[j-nums[i]]; } } return dp[sum]; }