网站建设岗位内容,中国建材信息总网,网站建设微商城,杭州微网站文章目录1. 题目2. 解题1. 题目
给定一个整数数组 nums 和一个正整数 k#xff0c;找出是否有可能把这个数组分成 k 个非空子集#xff0c;其总和都相等。
示例 1#xff1a;
输入#xff1a; nums [4, 3, 2, 3, 5, 2, 1], k 4
输出#xff1a; True
说明#xff1a;…
文章目录1. 题目2. 解题1. 题目
给定一个整数数组 nums 和一个正整数 k找出是否有可能把这个数组分成 k 个非空子集其总和都相等。
示例 1
输入 nums [4, 3, 2, 3, 5, 2, 1], k 4
输出 True
说明 有可能将其分成 4 个子集51,42,32,3等于总和。提示
1 k len(nums) 16
0 nums[i] 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 416. 分割等和子集动态规划
普通回溯超时59 / 149 个通过测试用例
class Solution {int target;bool ans false;int K;
public:bool canPartitionKSubsets(vectorint nums, int k) {int sum accumulate(nums.begin(), nums.end(), 0);K k;if(sum%k) return false;target sum/k;vectorint partsum(k, 0);dfs(nums, partsum, 0);return ans;}void dfs(vectorint nums, vectorint partsum, int i){if(ans true) return;if(i nums.size()){bool flag true;for(int k 0; k K; k){if(partsum[k] ! target){flag false;break;}}if(flag)ans true;return;}for(int j 0; j K; j){if(partsum[j]nums[i] target){partsum[j] nums[i];dfs(nums, partsum, i1);partsum[j] - nums[i];}}}
};优化从大到小排序可以尽快的让每个部分的和凑够
class Solution {int target;bool ans false;int K;
public:bool canPartitionKSubsets(vectorint nums, int k) {int sum accumulate(nums.begin(), nums.end(), 0);K k;if(sum%k) return false;target sum/k;sort(nums.rbegin(), nums.rend());//从大到小排序if(nums[0] target)//最大的数超过了不行return false;vectorint partsum(k, 0);dfs(nums, partsum, 0);return ans;}void dfs(vectorint nums, vectorint partsum, int i){if(ans true) return;if(i nums.size()){bool flag true;for(int k 0; k K; k){if(partsum[k] ! target){flag false;break;}}if(flag)ans true;return;}for(int j 0; j K; j){if(partsum[j]nums[i] target){partsum[j] nums[i];dfs(nums, partsum, i1);partsum[j] - nums[i];}}}
};168 ms 9.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
