public class Solution {
public boolean canPartition(int[] nums) {
// check edge case
if (nums == null  nums.length == 0) {
return true;
}
// preprocess
int volumn = 0;
for (int num : nums) {
volumn += num;
}
if (volumn % 2 != 0) {
return false;
}
volumn /= 2;
// dp def
boolean[] dp = new boolean[volumn + 1];
// dp init
dp[0] = true;
// dp transition
for (int i = 1; i <= nums.length; i++) {
for (int j = volumn; j >= nums[i1]; j) {
dp[j] = dp[j]  dp[j  nums[i1]];
}
}
return dp[volumn];
}
}
Java Solution similar to backpack problem  Easy to understand


nice solution ，there is a more concise version
public boolean canPartition(int[] nums) { if(nums == null  nums.length == 0) return true; int sum = 0; for(int n : nums) sum += n; if(sum % 2 != 0 ) return false; sum /= 2; boolean[] dp = new boolean[sum + 1]; dp[0] = true; // replace nums[i1] with nums[i] 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];
}
···

@tao62 You are amazing dude!
Adding the following line in inner for loop helped in improving time.if(dp[volumn]==true) return true;
We eliminate repeated calculations.

@phhoang Not really. I think the solution here is correct. Can you give any examples that prove it's wrong?

@aman13 This post has more details: https://chinmaylokesh.wordpress.com/2011/02/10/balancedpartitionproblemfindingtheminimizedsumbetweentwopartitionsofasetofpositiveintegers/

This solution fails (gives a runtime error) at the following test case:
[1,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296], i.e., a set of 2^i from i=0 to 32 with an extra 1.
How to fix this?

@tao62
good solution,but it has a bug,i think.
1 nums={INT_MAX,INT_MAX,INT_MAX...};or volumn>INT_MAX;
2 nums={INT_MAX1,1,1,INT_MAX1},the space complexity and the time complexity will be very big.

For people who are confused about this solution:
A good explanation:https://discuss.leetcode.com/topic/67539/01knapsackdetailedexplanation

Thanks to the author's solution! Very nice!
Also @ZhuEason Thanks for your solution! Your explanation are quite understandable by intoducing the 2D array way.
I hope I can make the solution more understandable.
I think the most tricky part would be:for (int i = 1; i <= nums.length; i++) { for (int j = volumn; j >= nums[i1]; j) { dp[j] = dp[j]  dp[j  nums[i1]]; } }
Since the problem is a 01 backpack problem, we only have two choices which are take or not. Thus in this problem, by using the sum value as the index of DP array, we transfer the problem to "whether should we take the currently visited number into the sum or not".
To construct the DP recurrence, when we are visiting nums[i] and to find partition of sum j: if we do not take the nums[i], then the current iteration does not make any difference on current DP value; if we take the nums[i], then we need to find whether the (new_sum = j  nums[i]) can be constructed. If any of this two construction can work, the partition of sum == j can be reached.Hope it helps.

My answer is as follows. Can I ask how you came up with the transition function? Or is it due to an optimization step? Thanks
bool canPartition(vector<int>& nums) {
long long sum=0;for (auto num : nums){ sum+=num; } if (sum%2nums.back()>sum/2) return false; sum/=2; int num=nums.size(); vector<vector<bool>> dp(sum+1,vector<bool>(num+1,false)); dp[0][0]=true; for (int i=0; i<=sum; i++){ for (int j=0; j<nums.size(); j++){ dp[i][j+1]=dp[i][j](i>=nums[j]?dp[inums[j]][j]:false); } } return dp[sum][num]; }

Does anyone know why this solution doesn't work? In the question
Path Sum iii
, we use this method tosum the path to a specific target
, and it works fine, but why it doesn't work here :\Thanks!
public boolean canPartition(int[] nums) { int sum = 0; for (int n : nums) sum += n; if ((sum & 1) != 0) return false; sum >>>= 1; Set<Integer> set = new HashSet(); set.add(0); Arrays.sort(nums); int s = 0; for (int n : nums) { s += n; set.add(s); if (set.contains(s  sum)) return true; } return false; }

nice solution. A couple optimizations you can make to it as follows.
First, someone else already pointed this one out. You can check for success within your elements loop (outer loop) to possibly terminate early.
Second, you can start your dp loop (inner loop) from a "max" position which is the lesser of the current sum of all elements used so far or the dp length.
public bool CanPartition(int[] nums) { int sum = 0; for (int i = 0; i < nums.Length; i++) sum += nums[i]; int target = sum / 2; if (target * 2 != sum) return false; bool[] dp = new bool[target + 1]; dp[0] = true; int currSum = 0; foreach (int x in nums) { int max = Math.Min(currSum + x, target); for (int j = max; j >= x; j) { dp[j] = dp[j]  dp[jx]; } if (dp[target] == true) return true; currSum += x; } return dp[target]; }

Even more concise and of course faster:
public boolean canPartition(int[] nums) { int sum = 0, n = nums.length; for (int num : nums) sum += num; if ((sum & 1) != 0) return false; sum >>>= 1; boolean[] dp = new boolean[sum + 1]; dp[0] = true; int curSum = 0; for (int x : nums) { int max = Math.min(sum, curSum += x); for (int j = max; j >= x; j) { dp[j] = dp[j]  dp[j  x]; } if (dp[sum] == true) return true; } return dp[sum]; }

@tao62 said in Java Solution similar to backpack problem  Easy to understand:
// dp transition for (int i = 1; i <= nums.length; i++) { for (int j = volumn; j >= nums[i1]; j) { dp[j] = dp[j]  dp[j  nums[i1]]; } }
Curious why we need
1based indexing
fori
.i
indicates which element in arraynums
is being under consideration. Sincei
's range is[0, n  1]
, why not simply for (int i = 0; i < nums.length; i++) { for (int j = volumn; j >= nums[i]; j) { dp[j] = dp[j]  dp[j  nums[i]]; } }

@tao62 thanks for your solution. this is good, and perhaps one of the most efficient solutions for this problem. However, I personally prefer ZhuEason's solution posted in the forum. His solution might be less efficient and longer in code... but it is more intuitive. It's very logical and straightforward. Whereas this solution relies on a hidden assumption which actually confused me for some time: The inner loop must proceed in reverse order because otherwise, we will overwrite our dp[j] calculations from the previous iteration of the outer loop. This is just kind of weird and atypical behavior for an algorithm in my opinion. So in my opinion, I will not recommend this approach. I recommend the more intuitive approach in this post:
https://discuss.leetcode.com/topic/67539/01knapsackdetailedexplanation