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

题意
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

思路：
①第一个想到的就是爆搜，把所有的元素放进k个集合里，直到所有的元素放完，同时要满足各个集合的元素和相等。这一点是很容易想到的。
②但是只爆搜，肯定要超时，所以就想怎么优化，即剪枝。这里剪枝的关键点在：如果当前集合元素的和等于前一个集合元素的和，那么对于元素nums[cnt]来说，其选择和前一个集合是一样的，所以可以不用再重复计算了。因为前一个集合s[i-1]回溯完后，进入下一个集合s[i]，此时要进行选择的元素下标依然是nums[cnt]，而nums[cnt]已经在上一个集合中计算过了，所以它在当前集合的选择和上一个集合的选择是一样的，没必要在重复计算了。详见代码。
代码

class Solution {
    final int N = 20;
    int[] s = new int[N];
    int avg,sum;
    int len;
    boolean flag;
     boolean dfs(int[] nums,int k,int cnt){
         if(cnt == len){
             //剪枝2，去除特判，只要最后所有的元素都进入各个集合中，那么集合中的和肯定满足要求
            //  for(int i = 0; i < k; i++){
            //      if(s[i] != avg)
            //         return false;
            //  }
             return true;
         }
         for(int i = 0; i < k; i++){
             //剪枝1，规定第一个元素放在第一个桶里
             if(i > 0 && cnt == 0) break;
             //重点：剪枝3，如果当前集合元素的和等于前一个集合元素的和，对于元素nums[cnt]来说，选择前一个集合或当前集合，结果是一样的。因为前一个集合s[i-1]回溯后，进入下一个集合s[i]，此时要进行选择的元素下标依然是nums[cnt]。
             if(i > 0 && (s[i] == s[i-1])) continue;
             if(s[i] + nums[cnt] <= avg){
                 s[i] += nums[cnt];
                 if(dfs(nums,k,cnt+1)){
                     return true;
                 }
                 s[i] -= nums[cnt];
             }
         }
         return false;
    }
    public boolean canPartitionKSubsets(int[] nums, int k) {
        len = nums.length;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % k != 0){
            flag = false;
        }else{
            avg = sum / k;
            flag = dfs(nums,k,0);
        }
        return flag;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44