# Java backpack solution

• This question can convert to 0 1 backpack question, the target is sum/k.

``````public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
int target = sum / k;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = target; i >= num; i--) {
dp[i] += dp[i - num];
}
}
return dp[target] >= k;
}
``````

• Brillant solution!

Could you explain why the final judging requirement is

``````return dp[target] >= k;
``````

``````return dp[target] == k;
``````

Thanks.

• This is incorrect. Consider the test case
`[1,1,1,1,1,1,6]`
`4`

The answer should be `false` while your solution output `true`

• I have same submission as posted here but have same doudt as @alcoholkid here. And the test case is failed.
So my question is can we convert this problem to a knapsack question?

• @alcoholkid Thanks for your test case. I modified the code, check again.

``````public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
int target = sum / k;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
// each num should be smaller than the target
if (num > target) {
return false;
}

for (int i = target; i >= num; i--) {
dp[i] += dp[i - num];
}
}
return dp[target] >= k;
}
``````

• @zy084232 said in Java backpack solution:

@alcoholkid Thanks for your test case. I modified the code, check again.

``````public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
int target = sum / k;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
// each num should be smaller than the target
if (num > target) {
return false;
}

for (int i = target; i >= num; i--) {
dp[i] += dp[i - num];
}
}
return dp[target] >= k;
}
``````

This is still incorrect. Check the test case
`[1,2,2,2,2]`
`3`
Until now, I don't believe this problem can be solved as a backpack problem. In your dp, you want to find out # of possible subsets that sum to target. However, these subsets considered in your codes can have overlapping. Thus, even if # of possible subsets is larger than k, you can not necessarily conclude the original array can be portioned into k `disjoint` subsets with a sum equal to target.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.