力扣leetcode 698. 划分为k个相等的子集

CSDN话题挑战赛第2期
参赛话题：算法题解

题目链接与描述

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;
    }  

结尾

欢迎评论区交流，每日打卡，冲冲冲！！！