You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the ith customer ordered. Determine if it is possible to distribute nums such that:
The ith customer gets exactlyquantity[i] integers,
The integers the ith customer gets are all equal, and
Every customer is satisfied.
Return true if it is possible to distribute nums according to the above conditions.
Example 1:
Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.
Example 2:
Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.
Example 3:
Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].
Constraints:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 105
There are at most 50 unique values in nums.
Solutions
Solution 1: State Compression Dynamic Programming + Subset Enumeration
First, we count the occurrence of each number in the array nums, and record it in the hash table cnt. Then we store the values in the hash table into the array arr. We denote the length of the array arr as n.
Note that the length of the array quantity does not exceed 10, so we can use a binary number to represent a subset of quantity. That is, the number j represents a subset of quantity, where the i-th bit of the binary representation of j is 1 means the i-th number in quantity is selected, and 0 means the i-th number is not selected.
We can preprocess an array s, where s[j] represents the sum of all numbers in the subset j of quantity.
Next, we define f[i][j] to represent whether the numbers in arr[0,..i-1] can be successfully allocated to the subset j of quantity, where i ranges from [0,..n-1], and j ranges from [0,2^m-1], where m is the length of quantity.
Considering f[i][j], if there exists a subset k in j such that s[k] <= arr[i], and f[i-1][j XOR k] is true, then f[i][j] is true, otherwise f[i][j] is false.
The answer is f[n-1][2^m-1].
The time complexity is O(n * 3^m), and the space complexity is O(n * 2^m). Here, n is the number of different integers in the array nums, and m is the length of the array quantity.