山西省财政厅门户网站三基建设,手机购买网站源码,seo沈阳,微信公众平台开发实例教程题意
给一个数组#xff0c;要求把数组里的元素分成k个子集#xff0c;满足每个子集中数的总和是相等的。问是否能分成k个子集
题目链接
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
思考
想象你有k个桶#xff0c;然后你有n个小球要求把数组里的元素分成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(vectorint nums, int k) {int sum 0;vectorint 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(), greaterint());return dfs(0, nums, b, a);}bool dfs(int u, vectorint nums, vectorint 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(u1, nums, b, a)) {return true;}b[i] - nums[u];}}return false;}
};时间复杂度 O ( k n ) O(k^n) O(kn)指数级
空间复杂度: O ( k ) O(k) O(k)
