Leetcode 698 Partition to K Equal Sum Subsets

题意

给一个数组，要求把数组里的元素分成k个子集，满足每个子集中数的总和是相等的。问是否能分成k个子集

题目链接

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

思考

想象你有k个桶，然后你有n个小球，你要做的是把这n个小球放进k个桶里，问能不能放成
最暴力的办法就是遍历所有的球，看看第一个桶能不能放，第二个桶能不能放。。。以此类推

题解

这k个子集每个子集的元素和假设为a。用dfs遍历，从第一个数字开始判断他应该放在哪个子集中。当当前子集的值小于等于需要的值的时候我们可以放，并且回溯。当最后一个数字被放入并且每个桶的元素和都能够满足为a时，那么就说明能够分成k份。
剪枝：1. 可以从大到小排序，这样可以先放大的数字，子集会更早达到元素和a
2. 当有两个子集的元素和相同时，我们只需要遍历一个子集就好
3. 当有子集的元素和已经满足为a，可以跳过

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

时间复杂度：$O(k^n)$指数级

空间复杂度:$O(k)$