classSolution{public:boolcanPartitionKSubsets(vector<int>&nums,intk){constintsum=accumulate(begin(nums),end(nums),0);if(sum%k!=0)returnfalse;constintt=sum/k;// Each subset's target sumreturndfs(nums,0,k,t,t,vector<bool>(nums.size()));}private:booldfs(constvector<int>&nums,ints,intk,inttarget,constintsubsetTargetSum,vector<bool>&&seen){if(k==0)returntrue;if(target<0)returnfalse;if(target==0)returndfs(nums,0,k-1,subsetTargetSum,subsetTargetSum,move(seen));for(inti=s;i<nums.size();++i){if(seen[i])continue;seen[i]=true;if(dfs(nums,i+1,k,target-nums[i],subsetTargetSum,move(seen)))returntrue;seen[i]=false;}returnfalse;}};
classSolution{publicbooleancanPartitionKSubsets(int[]nums,intk){finalintsum=Arrays.stream(nums).sum();if(sum%k!=0)returnfalse;finalintt=sum/k;// Each subset's target sumboolean[]seen=newboolean[nums.length];returndfs(nums,0,k,t,t,seen);}privatebooleandfs(int[]nums,ints,intk,inttarget,intsubsetTargetSum,boolean[]seen){if(k==0)returntrue;if(target<0)returnfalse;if(target==0)returndfs(nums,0,k-1,subsetTargetSum,subsetTargetSum,seen);for(inti=s;i<nums.length;++i){if(seen[i])continue;seen[i]=true;if(dfs(nums,i+1,k,target-nums[i],subsetTargetSum,seen))returntrue;seen[i]=false;}returnfalse;}}