😑698. Partition to K Equal Sum Subsets

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/submissions/

思路其实很巧妙很简单，要把nums分成k组，那我就dfs来决定每个元素放在哪个组(bucket)里就好了，超级容易TLE，防止TLE的关键是注释框起来那一行，如果在某个index这里某个bucket dfs到底了返回回来发现仍然是空的就可以直接return false了，不可能有解的。你可能在想我这个bucket可能根本没有进dfs呀，如果是那样的话由于现在bucket为空，说明有一个元素自身就比target大，那它分到哪一组都不可能，所以也不可能。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % k != 0) return false;
        int sum = total / k;
        int[] sums = new int[k];
        return dfs(nums, 0, sum, k, sums);
    }
    private boolean dfs(int[] nums, int index, int sum, int k, int[] sums) {
        if (index == nums.length) {
            for (int i = 0; i < k; i++) {
                if (sums[i] != sum) {
                    return false;
                }
            }
            return true;
        }
        for (int i = 0; i < k; i++) {
            if (sums[i] + nums[index] <= sum) {
                sums[i] += nums[index];
                //if we can fill all buckets then return true
                if (dfs(nums, index + 1, sum, k, sums)) return true;
                
                //means we can't fill other buckets if we take ith element 
                // so leave this element
                sums[i] -= nums[index];
            }
            // *********************IMPORTANT***********************
            if (sums[i] == 0) break;
            // *********************IMPORTANT***********************
        }
        return false;
    }
}