# 698. 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.

Example 1:

``````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.
``````

Note:

• `1 <= k <= len(nums) <= 16`.
• `0 < nums[i] < 10000`.

``````class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k != 0) return false;
vector<bool> visited(nums.size(), false);
return helper(nums, k, sum / k, 0, 0, visited);
}
bool helper(vector<int>& nums, int k, int target, int start, int curSum, vector<bool>& visited) {
if (k == 1) return true;
if (curSum == target) return helper(nums, k - 1, target, 0, 0, visited);
for (int i = start; i < nums.size(); ++i) {
if (visited[i]) continue;
visited[i] = true;
if (helper(nums, k, target, i + 1, curSum + nums[i], visited)) return true;
visited[i] = false;
}
return false;
}
};
``````

``````class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k != 0) return false;
sort(nums.begin(), nums.end(), greater<int>());
vector<bool> visited(nums.size(), false);
return helper(nums, k, sum / k, 0, 0, visited);
}
bool helper(vector<int>& nums, int k, int target, int start, int curSum, vector<bool>& visited) {
if (k == 1) return true;
if (curSum > target) return false;
if (curSum == target) return helper(nums, k - 1, target, 0, 0, visited);
for (int i = start; i < nums.size(); ++i) {
if (visited[i]) continue;
visited[i] = true;
if (helper(nums, k, target, i + 1, curSum + nums[i], visited)) return true;
visited[i] = false;
}
return false;
}
};
``````

``````class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k != 0) return false;
vector<int> v(k, 0);
sort(nums.begin(), nums.end());
return helper(nums, sum / k, v, (int)nums.size() - 1);
}
bool helper(vector<int>& nums, int target, vector<int>& v, int idx) {
if (idx == -1) {
for (int t : v) {
if (t != target) return false;
}
return true;
}
int num = nums[idx];
for (int i = 0; i < v.size(); ++i) {
if (v[i] + num > target) continue;
v[i] += num;
if (helper(nums, target, v, idx - 1)) return true;
v[i] -= num;
}
return false;
}
};
``````

Partition Equal Subset Sum

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/javacstraightforward-dfs-solution

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108751/easy-to-understand-java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation