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

题目：

给定一个整数数组  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] 范围内

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets
著作权归领扣网络所有。商业转载请联系官方授权，笔记非商业转载请注明出处。目编

思路：

先算出每个分组的入门和，然后分配k个桶，力扣每个桶的自学初始值为分组和，然后对排序后的笔记数组从大到小进行dfs判断是否可以加入某个桶，搜索完毕即全部分配。目编

代码：

class Solution {public:    bool canPartitionKSubsets(vector& nums, int k) {        if(k == 1)            return true;        int total = 0;        for(int & num : nums)             total += num;        if(total % k != 0)            return false;        total /= k;        sort(nums.begin(), nums.end());        vectorbuckets(k, total);        return dfs(k, nums, buckets, nums.size() - 1);    }    bool dfs(int k, vector& nums, vector& buckets, int idx) {        if(idx < 0)            return true;        for(int i = 0; i < k; i++) {            if(i >0 && buckets[i] == buckets[i - 1])                continue;            if(buckets[i] >= nums[idx]) {                buckets[i] -= nums[idx];                if(dfs(k, nums, buckets, idx - 1))                    return true;                buckets[i] += nums[idx];            }        }        return false;    }};