题目链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
题目描述：
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false
提示：
1 <= k <= len(nums) <= 160 < nums[i] < 10000- 每个元素的频率在
[1,4]范围内
解法：回溯+剪枝
首先我们可以计算出数组被平均分成k组，平均每组的和ave，判断数组是否能被平分。然后再对数组进行降序排序。当数组中的最大值大于 ave，那么也是不满足条件的。以上两种情况先过滤掉。
使用 falg 数组用来标记数组中那些元素被使用，然后开始我们的递归，依次从数组中获取一个元素累计相加和为temp，并将该元素标记为已使用。
- 若
temp = ave，则置 temp = 0，继续组合下一个分组。 - 若
temp < ave，则累加后继续遍历，寻找元素。 - 若
temp > ave，则跳过这次遍历，并取消标记。
当遍历完数组，没有找到合适的分组，那么就需要回溯，回溯的方法，将该元素置为未使用，并将 temp 减去该元素。
遍历过程中，使用剪枝，可以提升效率：
- 当该元素被标记已使用，则跳过。
- 当该元素值加上temp后大于ave，则跳过。
- 由于数组降序排序，所以在每组合一个分组时，只需要一直向后遍历即可。
代码：
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
int len = nums.length;
int ave = sum / k;
if (ave * k != sum) {
return false;
}
Integer[] numList = new Integer[len];
for (int i = 0; i < len; i++) {
numList[i] = nums[i];
}
Arrays.sort(numList, (a, b) -> b - a);
boolean[] falg = new boolean[len];
boolean dfs = dfs(numList, falg, ave, 0,0);
return dfs;
}
private boolean dfs(Integer[] nums, boolean[] falg, int ave, int temp,int n) {
boolean result = true;
for(boolean f : falg) {
result &= f;
}
if(result) {
return true;
}
for (int i = n; i < nums.length; i++) {
if(falg[i] || temp + nums[i] > ave) {
continue;
}
temp += nums[i];
falg[i] = true;
if(temp == ave) {
return dfs(nums,falg,ave,0,0);
}
boolean b = dfs(nums,falg,ave,temp,i+1);
if(!b) {
temp -= nums[i];
falg[i] = false;
} else {
return true;
}
}
return false;
}
}
