本文主要是介绍Partition to K Equal Sum Subsets问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.
示例:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
问题分析：
可以先求出数组和sum，看看是否能整除k，若不能，返回false，否则，遍历整个数组，看看是否能划分成k个子序列和相等的分割。
注意，这里对数组进行了降序排序。
过程详见代码：
class Solution {
public:bool canPartitionKSubsets(vector<int>& nums, int k) {int sum = accumulate(nums.begin(), nums.end(), 0);sort(nums.begin(), nums.end(), [](int a, int b){return a > b; });if (sum % k) return false;int t = sum / k;vector<bool> dp(nums.size(), false);int res = 0;for (int i = 0; i < nums.size(); i++){if (!dp[i] && dfs(dp, nums, t, i, 0)) res++;}return res == k;}bool dfs(vector<bool>& dp, vector<int>& nums, int target, int start,int sum){if (sum == target) {return true;}for (int i = start; i < nums.size(); i++){if (!dp[i]){dp[i] = true;bool b = dfs(dp, nums, target, i + 1, sum + nums[i]);if (!b) dp[i] = false;else return true;}}return false;}
};
这篇关于Partition to K Equal Sum Subsets问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
