# share DP solution using Java, time complexity O(N*(2^N))!

• ``````class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
if(k==1){
return true;
}
int sum = Arrays.stream(nums).sum();
if(sum%k!=0){
return false;
}

int target = sum/k;

Boolean[] dp = new Boolean[1<<nums.length];
int[] total = new int[1<<nums.length];
return searchHelper(dp,total,nums,0,target);

}

public boolean searchHelper(Boolean[] dp,int[] total,int[] nums,int state,int target){
if(dp[state]!=null){
return dp[state];
}

if(state==(1<<nums.length)-1){
if(total[state]==0){
return true;
}else{
return false;
}
}

for(int i=0;i<nums.length;i++){
if(((state>>i)&1)==0){
int future = (state|(1<<i));
if(total[state]+nums[i]<=target){
total[future] = (total[state]+nums[i])%target;
if(searchHelper(dp,total,nums,future,target)){
dp[state] = true;
return true;
}
}
}
}

dp[state] = false;
return false;
}
}
``````

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