698.划分为k个相等的子集（难度：中等）

题目链接：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) <= 16
• 0 < 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;
    }
}