题目
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
解题
方法一：回溯
这道题的其实和之前的也不太一样，名字中有子集，其实又不是子集问题。不是找出所有情况。另外这个可以说是一种组合问题，但是不是找到所有的组合。
核心是：每次找到一组和，后重头开始遍历，而不是回溯！使用used记录是否使用过，这里的used是全局的。
leetcode-47：全排列 II中的used是针对每个path的，而此题used是针对整个结果的。
当找到的一组和，不满足的时候才使用的是回溯
其实，想简单点，就是每次找到一组和=target的时候，就重新开始找下一组，利用used作为mask，把遍历过的就不再使用了。
class Solution { public: bool backtracing(vector<int>& nums,int k,int target,int sum,int startIndex,vector<bool>& used){ if(k==0) return true; if(sum==target){ return backtracing(nums,k-1,target,0,0,used); } for(int i=startIndex;i<nums.size();i++){ if(!used[i]&&sum+nums[i]<=target){ used[i]=true; if(backtracing(nums,k,target,sum+nums[i],i+1,used)) return true; used[i]=false; } } return false; } bool canPartitionKSubsets(vector<int>& nums, int k) { vector<bool> used(nums.size()); int sum=accumulate(nums.begin(),nums.end(),0); if(sum%k!=0) return false; int target=sum/k; for(int num:nums){//新添加的 if(num>target) return false; } return backtracing(nums,k,target,0,0,used); } };
当然for循环的第一句sum+nums[i]<=target是剪枝
当然也可以剪枝换个地方,比如这样剪枝
if(sum==target){ return backtracing(nums,k-1,target,0,0,used); } else if(sum>target) return false;
后续力扣对测试样例了，如果不添加这行，会导致超时。
for(int num:nums){//新添加的 if(num>target) return false; }
java
//i=startIndex只是为了提速，否则会超时
class Solution { boolean dfs(int[] nums,boolean[] used,int startIndex,int sum,int target,int k){ if(k==0) return true; if(sum==target){ return dfs(nums,used,0,0,target,k-1); } for(int i=startIndex;i<nums.length;i++){ if(used[i]==true||sum+nums[i]>target) continue; used[i]=true; if(dfs(nums,used,i+1,sum+nums[i],target,k)) return true; used[i]=false; } return false; } public boolean canPartitionKSubsets(int[] nums, int k) { int sum=0; for(int i=0;i<nums.length;i++){ sum+=nums[i]; } if(sum%k!=0) return false; int target=sum/k; boolean[] used=new boolean[nums.length]; for(int num:nums){ if(num>target) return false; } return dfs(nums,used,0,0,target,k); } }
