题目
给定一个整数数组 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] 范围内
思路
借鉴了官方题解的思路
状态压缩+记忆化搜索，其实就是利用DFS填k个桶，每层都检查一下所有的数哪些没有用，没有使用过就尝试填入当前的桶。由于最多只有16个数，所以可以用一个整型来表示各个数字的使用状态，1表示当前数字已经填过，0表示当前数还未被使用。
题解
class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: all = sum(nums) if all % k: return False per = all // k nums.sort() # 方便下面剪枝 if nums[-1] > per: return False n = len(nums) @cache def dfs(s, p): if s == 0: return True for i in range(n): if nums[i] + p > per: break if s >> i & 1 and dfs(s ^ (1 << i), (p + nums[i]) % per): # p + nums[i] 等于 per 时置为 0 return True return False return dfs((1 << n) - 1, 0)
