leetcode 698.划分为k个相等的子集

698. 划分为k个相等的子集
难度
中等

833

给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false
 

提示：

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

思路:

暴力搜索＋剪枝

首先如果该集合能够被划分为k个相等的子集，那么其所有元素的和一定被k整除，我们首先遍历整个数组 计算出所有元素的和计算每个子集的值

采用桶球的模型来分析

对于每一个球我们需要将其放入一个桶中，最后得到和相同的k个桶

那么我们逐一枚举每一个球的情况，观察其能够放入当前桶中，如果可以放进去，递归放后面的球，如果其不能放入任何一个桶，递归返回 寻找下一种可行方案，直到遍历完所有的情况最后从第一个球处返回结果   本质是暴力搜索加剪枝

回溯算法的一般思路

我们需要思考三个问题

1.路径 也就是已经做出的选择

2.选择列表：当前可以做出的选择

3.结束条件：到达决策树的底层，无法再做选择的条件

决策树

 我们在每个节点上都在做决策

回溯算法的一般模板

参考  https://labuladong.github.io/algo/4/31/106/

在许多情况下直接使用暴力搜素回溯会超时，这个时候需要我们根据题目的要求进行合理的剪枝来适当降低算法的情况

我们先来看具体代码

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        //数组的前缀和？
        int sum = 0;
        for (auto& num : nums) {
            sum += num;
        }
        //如果数组总和不能被k整除 那么一定不可分
        if (sum % k) return false;
        int target=sum/k;
        //排序数组 从前往后枚举
        int*bucket=new int[k];
　　　　　//此处为第一个剪枝 我们可以看到往下一层递归的条件是 当前的球放进桶内小于或者等于所要达到的和
        //那么根据决策树的特点 我们在将数组从大到小排序，树的上层数字越大越容易触发 当前球放进去后比所求的和要大的剪枝条件
        sort(nums.begin(),nums.end(),greater<int>());
        for(int i=0;i<k;i++) bucket[i]=0;
        return backtrack(0,bucket,k,nums,target);
    }
    bool backtrack(int index,int bucket[],int k,vector<int>&nums,int target){
        if(index==nums.size()){
              return true;
        }
        for(int i=0;i<k;i++){
            //此处为第二处剪枝 如果当前桶和上一个桶的值是相同的 因为我们是顺序遍历球 那么后续目标和后续可选择列表对于两个桶都是一样的 
　　　　　　　　//也就是说 当前桶需要暴力搜索的情况，在上一个桶时我们已经搜索过了 剪枝
             //同时此处还隐含了另外一个剪枝，对于第一个球，我们将其放入任何一个桶情况都是一样的，所以并且其在决策树的顶部 所以我们不妨直接将其放入第一个桶中.
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;
            if(bucket[i]+nums[index]>target) continue;
            bucket[i]+=nums[index];
            if(backtrack(index+1,bucket,k,nums,target)) return true;
            bucket[i]-=nums[index];
        }
        return false;
    }
};