leetcode：698. 划分为k个相等的子集【暴搜 + 排序 + 剪枝优化题】

分析

分为k个桶
首先tot要被k整除，得到每个桶的target
然后最大值不能超
之后就可以开始记忆化dfs了
用rest表示桶的剩余位置，restSum表示还剩多少个可以放
如果cur到达n，且restSum为0，说明是一种成功方法
其他就是失败False
然后就开始放cur的球
我们可以排序rest进行优化，从大到小
所以从头可以放的，如果不能放就break
还有一个优化点就是去重，相邻的桶相等的也可以continue掉
注意球的大小最好也要逆序排，为的是赶紧把空间占满

ac code

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        tot = sum(nums)
        if tot % k != 0:
            return False
        target = tot // k
        if max(nums) > target:
            return False
        nums.sort(reverse = True)
        
        rest = [target] * k

        @cache
        def dfs(now, rest, restSum):
            rest = list(rest)
            if now == n and restSum == 0:
                return True
            
            if now >= n:
                return False
            
            res = False
            # 暴搜所有可以的放法
            # 1.排序优化（因为只有16）
            # 只能放有的
            rest.sort(reverse = True)
            for i in range(k):
                # 2.去重优化
                if i > 0 and rest[i] == rest[i - 1]:
                    continue
                if rest[i] >= nums[now]:
                    rest[i] -= nums[now]
                    res |= dfs(now + 1, tuple(rest), restSum - nums[now])
                    rest[i] += nums[now]
                else:
                    break
            
            return res
        
        return dfs(0, tuple(rest), tot)
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

总结

暴力搜索 + 排序优化 + 去重优化
就是dfs各种剪枝
从大到小排序很重要哦