LeetCode-698. 划分为k个相等的子集【数组,回溯】
2023-09-14 09:01:27 时间
题目描述:
给定一个整数数组 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] 范围内
解题思路一:剪枝很重要,从大到小排序可以命中if (bucket[i] + nums[index] > target) 这个剪枝。二 。// 如果 当前子集的元素和 与 前一个子集的元素和 是一样的,那就跳过 if(i > 0 && bucket[i] == bucket[i-1]){ continue; }也是一个剪枝。三。最后将所有数放入子集中,那么可以直接返回true。
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
if(k > nums.size()) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % k != 0) return false;
// 从大到小放数字
sort(nums.rbegin(), nums.rend());
// 记录每个子集中数字之和
bucket.resize(k);
// 每个桶中的数字之和应该为target
int target = sum/k;
// index = 0, 表示从0号元素开始遍历
return backtrack(nums, 0, target);
}
private:
// 记录每个子集中数字之和
vector<int> bucket;
bool backtrack(vector<int> &nums, int index, int target){
// 如果所有数字遍历完了
if(index == nums.size()){
// 既然所有数字都放进集合中了,那么所有bucket中的元素和一定为target。所以下面这个循环是没有必要的:
// 检查所有子集中的数字之和是否都是target
// for(int i = 0; i < bucket.size(); i++){
// if(bucket[i] != target){
// return false;
// }
// }
return true;
}
// 注意:i 表示第i个子集,index 表示第index个数字
for(int i = 0; i < bucket.size(); i++){
// 如果这个数字放入子集i中使子集i中元素和超出target了
if(bucket[i] + nums[index] > target){
continue;
}
// 如果 当前子集的元素和 与 前一个子集的元素和 是一样的,那就跳过
if(i > 0 && bucket[i] == bucket[i-1]){
continue;
}
// 将数字放入子集i中
bucket[i] += nums[index];
// 递归穷举下一个数字的情况
if(backtrack(nums, index + 1, target)){
return true;
}
// 撤销选择
bucket[i] -= nums[index];
}
// 如果 nums[index] 放入哪个子集都不行
return false;
}
};
解题思路二:暂无
解题思路三:暂无
相关文章
- LeetCode每日一题-5:删除排序链表中的重复元素
- ☆打卡算法☆LeetCode 207. 课程表 算法解析
- <leetcode刷题-数组> 【双指针】旋转数组
- Leetcode 差分数组的应用「建议收藏」
- LeetCode题解——和为 k 的子数组
- LeetCode周赛298,阳光普照,参加就能简历免筛
- leetcode-26删除有序数组中的重复项(双指针)「建议收藏」
- LeetCode 26. 删除排序数组中的重复项
- LeetCode 1389. 按既定顺序创建目标数组
- LeetCode 2195. 向数组中追加 K 个整数(贪心)
- JavaScript刷LeetCode心得
- JavaScript刷LeetCode拿offer-js版字典_2023-02-28
- LeetCode - #74 搜索二维矩阵
- LeetCode 26:删除有序数组中的重复项
- Leetcode 560. 和为 K 的子数组
- 每日一道leetcode:4. 寻找两个正序数组的中位数
- leetcode每日一练:旋转数组
- LeetCode每日一练:数组中重复的数字