https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
给定一个整数数组 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 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内
首先计算总和sum,若总和无法除尽k,则说明分配一定失败。
每个子集总和为goal = sum/k
dfs:
剪枝:
如此的dfs一定是爆炸的,接下来进行剪枝,有两个剪枝原则:
class Solution {
public:
bool dfs(int idx, vector<int>& nums, vector<bool>& mark, int goal, int sum,int k){
/*
* idx: 当前尝试添加数组中的idx位置元素
* nums: 输入整数组
* mark: 标记每一个位置整数是否被使用
* goal: 每个子集的总和
* sum: 当前子集的总和,达到即可进入下一个子集
* k: 当前剩余的待填满的子集个数
* dfs递归剪枝:dfs每一层尝试对当前子集填充每个数(已使用的跳过,超过子集的和跳过),
* 若子集可以容纳下该数,继续dfs;若子集容纳该数后达到goal,则进入下一个子集进行填充
* 注意剪枝策略:
* ①遍历下一层的数时,选择比当前数小的点(事先排序则从idx+1开始遍历),
* 重新开始一个子集需要从最大的数开始遍历
* ②子集才开始装元素,此时若最大的元素无法装入,那么一定容纳不下该元素,如8要装入容量为5的所有子集
*/
cout<<idx<<" "<<sum<<" "<<k<<endl;
if(k == 0) return true; // 所有子集填满了
if(goal == sum) return dfs(0, nums, mark, goal, 0, --k ); // 填满一个子集,进入下一个子集
for(int i = idx; i<nums.size(); i++){
if(mark[i]) continue; // 已使用此点
if(sum + nums[i] > goal) continue; // 超过子集的容量
mark[i] = true;
if(dfs(i+1, nums, mark, goal, sum+nums[i], k)) return true; // 将i放入集合中,注意下一个点从(i+1)开始,因为这个集合不可能容纳比nums[i]还大的元素了(nums提前排序了的)
mark[i] = false; // 回溯
if(sum == 0) return false; // sum==0表示此子集才开始装元素,此时若最大的元素无法装入,那么一定容纳不下该元素,如8要装入容量为5的所有子集
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for(int i = 0; i < nums.size(); i++) sum += nums[i];
if(sum%k) return false; // 不可除清说明一定分配不均匀
vector<bool> mark(nums.size(), 0); // 标记是否使用
sort(nums.begin(), nums.end(), greater<int>()); // 排序使得每次访问可以更优
return dfs(0, nums, mark, sum/k, 0, k);
}
};