title
给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：
- 第
i位顾客 恰好 有quantity[i]个整数。 - 第
i位顾客拿到的整数都是 相同的 。 - 每位顾客都满足上述两个要求。
如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。
示例 1：
输入：nums = [1,2,3,4], quantity = [2]
输出：false
解释：第 0 位顾客没办法得到两个相同的整数。
示例 2：
输入：nums = [1,2,3,3], quantity = [2]
输出：true
解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3：
输入：nums = [1,1,2,2], quantity = [2,2]
输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。
示例 4：
输入：nums = [1,1,2,3], quantity = [2,2]
输出：false
解释：尽管第 0 位顾客可以得到 [1,1] ，第 1 位顾客没法得到 2 个一样的整数。
示例 5：
输入：nums = [1,1,1,1,1], quantity = [2,3]
输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [1,1,1] 。
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= 1000m == quantity.length1 <= m <= 101 <= quantity[i] <= 105nums中至多有50个不同的数字。
solution
类似选帽子，枚举子集。
class Solution:
def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
n2 = len(quantity)
dp = [False] * (1 << n2)
dp[0] = True
fsum = [0] * (1 << n2)
for i in range(1 << n2):
fsum[i] = sum(quantity[j] for j in range(n2) if (1 << j) & i)
counter = collections.Counter(nums)
d = list(counter.keys())
for k in range(len(d)):
v = counter[d[k]]
for mask in range((1 << n2) - 1, -1, -1):
rest = (1 << n2) - 1 - mask
sub = rest
if not dp[mask]: continue
while sub:
if fsum[sub] <= v:
dp[mask | sub] = True
sub = (sub - 1) & rest
return dp[(1 << n2) - 1]