给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。
输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
输入: nums = [1,2,3,4], k = 3
输出: false
1
来源:力扣(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());
vector buckets(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;
}
};
Original: https://blog.csdn.net/DK_Sorhic/article/details/126960095
Author: DK_Sorhic
Title: 入门力扣自学笔记155 C++ (题目编号698)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/542391/
转载文章受原作者版权保护。转载请注明原作者出处!