Partition to K Equal Sum Subsets
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.
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
Constraints:
- 1 <= k <= nums.length <=
16
- 1 <= nums[i] <= 104
- The frequency of each element is
in the range [1, 4].
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < nums.length; i++){
sum += nums[i];
}
for (int i = 1; i <= sum/k; i++) {
List<List<Integer>> subsets = new ArrayList<>();
for (int j = 0; j < k; j++){
subsets.add(new ArrayList<Integer>());
}
Arrays.sort(nums);
if (insertRecursively(subsets,
nums, i, 0))
return true;
}
}
return false;
}
public boolean insertRecursively(List<List<Integer>> subsets, int[] nums, int sum, int index) {
if (index == nums.length &&
valid(subsets, sum)) {
return true;
}
}
for (int i = 0; i < subsets.size(); i++){
int subsetSum = 0;
for (int j = 0; j < subsets.get(i).size(); j++){
subsetSum += subsets.get(i).get(j);
}
if (subsetSum + nums[index]
<= sum){
subsets.get(i).add(nums[index]);
if (insertRecursively(subsets,
nums, sum, index+1)) {
return true;
}
subset.get(i).remove(subset.get(i).size()-1);
}
}
return false;
}
public boolean valid(List<List<Integer>> subsets, int sum){
for (int i = 0; i < subsets.size(); i++){
int subsetSum = 0;
for (int j = 0; j < subsets.get(i).size(); j++){
subsetSum += subsets.get(i).get(j);
}
if (subsetSum != sum){
return false;
}
}
return true;
}
}
