698. Partition to K Equal Sum Subsets
1. Description
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
2. Example
Example 1
Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Example 2
Input: nums = [1,2,3,4], k = 3
Output: false
3. Constraints
- 1 <= k <= nums.length <= 16
- 1 <= nums[i] <= 10$^4$
- The frequency of each element is in the range [1, 4].
4. Solutions
Backtracking
n = nums.size()
Time complexity: O(k$^n$)
Space complexity: O(kn)
class Solution {
public:
bool canPartitionKSubsets(vector<int> nums, int k) {
const int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k != 0) {
return false;
}
sort(nums.rbegin(), nums.rend());
const int target = sum / k;
if (nums.front() > target) {
return false;
}
vector<int> buckets(k, 0);
return able_to_assign(nums, 0, target, buckets);
}
private:
bool able_to_assign(const vector<int> &nums, int index, int target, vector<int> &buckets) {
if (index == nums.size()) {
return true;
}
int num = nums[index];
unordered_set<int> visited;
for (int i = 0, k = buckets.size(); i < k; ++i) {
if (!visited.contains(buckets[i]) && buckets[i] + num <= target) {
visited.insert(buckets[i]);
buckets[i] += num;
if (able_to_assign(nums, index + 1, target, buckets)) {
return true;
}
buckets[i] -= num;
}
}
return false;
}
};