题目链接与描述

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个非空子集总和相等，总和可以知道为：sum(nums)/k = 子集之和m
如果这里余数不为0，个相说明无法均分
同时元素大于0，力扣最大值比m大也无法凑齐
可以想到，划分先排序后，个相双指针求和，力扣凑齐集合使它等于m
但是划分左指针需要尽可能将大的匹配掉，因为小的个相可以多几个组成平均值，大数无法组，而左指针是根据右指针开始，所以使用一个序号去递归遍历即可
开始，预先变量存储，后面需要递归，避免传参麻烦

int[] numsField;    int index, avg, kNum;        public boolean canPartitionKSubsets(int[] nums, int k) {                 numsField = nums;        kNum = k;        int total = 0;        // 计算总值        for (int x : numsField) {             total += x;        }        // 平均值不等显然无法凑齐        if (total % kNum != 0) {             return false;         }        // 排序后遍历        Arrays.sort(numsField);        index = numsField.length; avg = total / kNum;        return dfs(index - 1, 0, 0, new boolean[index]);    }    boolean dfs(int idx, int currentSum, int countK, boolean[] vis) {         // 如果统计的k数等于预期的，完成        if (countK == kNum) {             return true;        }        // 如果当前累积已经满足平均值，接着遍历下一个数        if (currentSum == avg) {             return dfs(index - 1, 0, countK + 1, vis);        }        // 如果遍历完成，却cur不等avg        if (idx == -1) {             return false;        }        // 继续迭代，遍历查询        for (int i = idx; i >= 0; i--) {              // 访问过 或者 大于 显然不符合            if (vis[i] || currentSum + numsField[i] >avg) {                 continue;            }            // 小于或者等于 则设为访问过            vis[i] = true;            // 将下一个推入，如果是符合的则返回true            if (dfs(i - 1, currentSum + numsField[i], countK, vis)) {                 return true;            }            // 不符合要将恢复false ， 可能存在后续的数组使用            vis[i] = false;            // 当前累积值如果是0 直接返回false 说明已经没有数了            if (currentSum == 0) {                 return false;             }        }        // 最后都没有找到        return false;    }