划分K个相等的子集

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] 范围内

解题思路

同473. 火柴拼正方形，只不过本题用k个桶装小球

若k=4，如图，站在小球的视觉，每个小球可以放入任意的桶，桶的容量为sum/4，每一层代表每个小球的选择，若找到一条能放满小球的路径，返回true。

容易得出回溯代码，但该该代码的时间复杂度达到O(k^n)，如果不进行剪纸优化，必定超时

public boolean backtracking(int[] nums, int[] buckets, int index, int size){
        if(index == nums.length){
            return true;
        }

        for(int i = 0 ; i<buckets.length; i++){ //每个球遍历k个桶，如果放不下放下一个桶，放得下继续放
            if(buckets[i] + nums[index] > size){
                continue; //剪枝
            }
            buckets[i] += nums[index];
            if(backtracking(nums, buckets, index+1, size)){
                return true;
            }
            buckets[i] -= nums[index];
        }
        return false; //k个桶都放不下，返回false
    }

故我们将nums数组进行逆序排序，减少搜索量

public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % k != 0) return false;//不能分成k段
        Arrays.sort(nums); 
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) { //数组逆序排序，减少搜索量
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int[] buckets = new int[k]; //创建k个桶
        return backtracking(nums, buckets, 0, sum/k);
        
    }

但是仍然会超时，此时我们进行第二次优化

如果当前桶和上一个桶内的元素和相等，则跳过

原因：如果元素和相等，那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的

for (int i = 0; i < buckets.length; i++) {
    // 如果当前桶和上一个桶内的元素和相等，则跳过
    // 原因：如果元素和相等，那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
    if (i > 0 && bucket[i] == bucket[i - 1]) continue;
    // 其他逻辑不变
}

代码

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum%k != 0) return false;//不能分成k段
        Arrays.sort(nums); 
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) { //数组逆序排序，减少搜索量
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        int[] buckets = new int[k]; //创建k个桶
        return backtracking(nums, buckets, 0, sum/k);
        
    }

    public boolean backtracking(int[] nums, int[] buckets, int index, int size){
        if(index == nums.length){
            return true;
        }

        for(int i = 0 ; i < buckets.length; i++){ //每个球遍历k个桶，如果放不下放下一个桶，放得下继续放
            // 如果当前桶和上一个桶内的元素和相等，则跳过
            // 因为nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
            if (i > 0 && buckets[i] == buckets[i - 1]) {
                continue;
            }
            if(buckets[i] + nums[index] > size){
                continue; //剪枝
            }
            buckets[i] += nums[index];
            if(backtracking(nums, buckets, index+1, size)){
                return true;
            }
            buckets[i] -= nums[index];
        }
        return false; //k个桶都放不下，返回false
    }
}

• 时间复杂度：$O(k^n)$，其中 k 是划分子集的数量，即桶的个数，n个数可以选择放在k个桶上
• 空间复杂度：$O(n)$，n为递归栈需要的空间