698. 划分为k个相等的子集【中等】

给定一个整数数组 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] 范围内

题解：

public class PartitionToKEqualSumSubsets {
    int[] nums;
    // n为数组元素个数，t为每个子集的和，k为分为k份
    int n, t , k;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        int total = 0;
        for (int num : nums) {
            total += num;// 计算所有元素之和
        }
        // 不能整除
        if (total % k != 0) {
            return false;
        }
        this.t = total / k;
        Arrays.sort(this.nums);
        this.n = this.nums.length;
        return dfs(n - 1, 0, 0, new boolean[n]);
    }

    /**
     *
     * @param index 当前元素位置
     * @param curTotal 当前子集的元素之和（初始为0）
     * @param curCount 当前已凑成总和为t的子集个数
     * @param vis 当前已被使用的元素
     * @return boolean
     */
    private boolean dfs(int index, int curTotal, int curCount, boolean[] vis) {
        if (curCount == k) {
            return true;
        }
        if (curTotal == t) {
            return dfs(n -1, 0, curCount + 1, vis);
        }
        // 从大到小搜索
        for (int i = index; i >= 0; i--) {
            if (vis[i] || curTotal + nums[i] > t) {// 不符合条件
                continue;
            }
            // 将nums[i]计算一遍
            vis[i] = true;
            if (dfs(i - 1, curTotal + nums[i], curCount, vis)) {
                return true;
            }
            vis[i] = false;
            if (curTotal == 0) {
                return false;
            }
        }
        return false;
    }
}

题解来源：【宫水三叶の相信科学系列】一题双解 :「搜索 + 剪枝」&「模拟退火」

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。