虽然说是中等题，但是感觉比昨天那道hard的图论还难錒...
是可以用状态压缩dp写的，但是我还没学这个。但是这题剪枝真的离谱，优化到最简可以从超时优化到0ms
但是如果说是纯搜索
这个剪枝和递归过程还是很值得学习的....
这题的搜索有两种思路，把题目看作将数装进k个桶。
一种是从桶出发 ，一个一个桶的枚举要放什么数。
另一种是从数出发，枚举这个数要放在哪个桶里。
分析第二种思路。
以数组为[10,10,10,7,7,7,7,7,7,6,6,6]，分成3部分为例， 即分成3个桶，每个桶的和为30 排序后数组为[6,6,6,7,7,7,7,7,7,10,10,10]，需要放在3个桶中，每个桶的和为30 第一层递归，末尾的10放在第一个桶中 | | | | | | | | | | | | | | | | | | |10 | | | | | --- --- --- 桶1 桶2 桶3 第二层和第三层递归，倒数第二个和倒数第三个10都放在桶1中 | | | | | | |10 | | | | | |10 | | | | | |10 | | | | | --- --- --- 桶1 桶2 桶3 第四层递归，倒数第一个7就不能放在桶1中了，因为30+7>30 所以放在桶2中 | | | | | | |10 | | | | | |10 | | | | | |10 | |7 | | | --- --- --- 桶1 桶2 桶3 后续直到桶2中放了4个7， | | |7 | | | |10 | |7 | | | |10 | |7 | | | |10 | |7 | | | --- --- --- 桶1 桶2 桶3 再有7就不能放到桶2中了，因为5*7>30 后续的2个7和2个6放到了桶3中 | | |7 | |6 | |10 | |7 | |6 | |10 | |7 | |7 | |10 | |7 | |7 | --- --- --- 桶1 桶2 桶3 正数第一个6这时没地方放了，因为放到任何一个桶中，都大于30 这时遍历3个桶，都没法放进去之后，返回false 然后递归返回， 递归返回到正数第二个6，正数第二个6从桶3中出栈，但是没有桶4可以让正数第二个6放进去了， for循环直接结束了，同时返回false 同理，桶3中的元素会依次从桶3中出栈 然后桶2中的栈顶的7，会尝试放到桶3中，再递归下去，（剩余的数组元素为[6,6,6,7,7]) 当然我们知道这种情况也是无解的， | | | | | | |10 | |7 | | | |10 | |7 | | | |10 | |7 | |7 | --- --- --- 桶1 桶2 桶3 最终桶2中的元素，会全部依次出栈，此时数组中剩余的元素为[6,6,6,7,7,7,7,7,7] | | | | | | |10 | | | | | |10 | | | | | |10 | | | | | --- --- --- 桶1 桶2 桶3 如果没有 if (groups[i] == 0) break; 这行代码 我们知道了桶2已经是空了，但是仍然会运行for循环，把倒数第一个位置的7，放到桶3中再次尝试，并继续递归下去 但是这样其实没有意义，因为桶2和桶3的地位是一样的， 这种情况也是无解的，所以可以剪枝 同样，桶1中的栈顶的2个10都会出栈，最终会平均分配到3个桶中，剩余的元素，也都会平均分配到每个桶中 |6 | |6 | |6 | |7 | |7 | |7 | |7 | |7 | |7 | |10 | |10 | |10 | --- --- --- 桶1 桶2 桶3 最后一次递归的时候 row就是-1了，这时直接返回true
class Solution {
public:
int buk[17];
bool canPartitionKSubsets(vector& nums, int k) {
int t=accumulate(nums.begin(),nums.end(),0);
if(t%k!=0)return 0;//如果不不能整除k直接返回0
int p=t/k;
sort(nums.begin(),nums.end(),[](int a,int b){
return a>b;//排序优化
});
return dfs(0,p,nums,k);//dep为当前处理的数字
}
int dfs(int dep,int p,vector&arr,int k){
if(dep==arr.size())return 1;
if(arr[dep]>p)return 0;
for(int j=1;j<=k;j++){
if(buk[j]+arr[dep]<=p){
buk[j]+=arr[dep];
if(dfs(dep+1,p,arr,k))return 1;
buk[j]-=arr[dep];
}
if(buk[j]==0)return 0;//删除无意义的递归
}
return 0;
}
};
