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].
Example 4:
Input: nums = [1,1,2,3], quantity = [2,2] Output: false Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.
Example 5:
Input: nums = [1,1,1,1,1], quantity = [2,3] Output: true Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].
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 innums
.
Solution1: Backtracking
Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)
C++
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 |
// Author: Huahua class Solution { public: bool canDistribute(vector<int>& nums, vector<int>& quantity) { unordered_map<int, int> m; for (int x : nums) ++m[x]; vector<int> cnt; for (const auto& [x, c] : m) cnt.push_back(c); const int q = quantity.size(); const int n = cnt.size(); function<bool(int)> dfs = [&](int d) { if (d == q) return true; for (int i = 0; i < n; ++i) if (cnt[i] >= quantity[d]) { cnt[i] -= quantity[d]; if (dfs(d + 1)) return true; cnt[i] += quantity[d]; } return false; }; sort(rbegin(cnt), rend(cnt)); sort(rbegin(quantity), rend(quantity)); return dfs(0); } }; |
Solution 2: Bitmask + all subsets
dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.
Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)
C++
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 |
class Solution { public: bool canDistribute(vector<int>& nums, vector<int>& quantity) { vector<int> cnt; unordered_map<int, int> freq; for (int x : nums) ++freq[x]; for (const auto& [x, f] : freq) cnt.push_back(f); const int n = cnt.size(); const int m = quantity.size(); vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n)); vector<int> sums(1 << m); for (int mask = 0; mask < 1 << m; ++mask) for (int i = 0; i < m; ++i) if (mask & (1 << i)) sums[mask] += quantity[i]; function<bool(int, int)> dp = [&](int mask, int i) -> bool { if (mask == 0) return true; if (i == n) return false; auto& ans = cache[mask][i]; if (ans.has_value()) return ans.value(); int cur = mask; while (cur) { if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) { ans = true; return true; } cur = (cur - 1) & mask; } ans = dp(mask, i + 1); return ans.value(); }; return dp((1 << m) - 1, 0); } }; |
Python3
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 |
# Author: Huahua class Solution: def canDistribute(self, nums: List[int], quantity: List[int]) -> bool: cnts = list(Counter(nums).values()) m = len(quantity) n = len(cnts) sums = [0] * (1 << m) for mask in range(1 << m): for i in range(m): if mask & (1 << i): sums[mask] += quantity[i] @lru_cache(None) def dp(mask: int, i: int) -> bool: if not mask: return True if i < 0: return False cur = mask while cur: if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1): return True cur = (cur - 1) & mask return dp(mask, i - 1) return dp((1 << m) - 1, n - 1) |
Bottom up:
C++
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 |
class Solution { public: bool canDistribute(vector<int>& nums, vector<int>& quantity) { vector<int> cnt; unordered_map<int, int> freq; for (int x : nums) ++freq[x]; for (const auto& [x, f] : freq) cnt.push_back(f); const int n = cnt.size(); const int m = quantity.size(); vector<int> sums(1 << m); for (int mask = 0; mask < 1 << m; ++mask) for (int i = 0; i < m; ++i) if (mask & (1 << i)) sums[mask] += quantity[i]; // dp[mask][i] := use first i types to satisfy mask customers. vector<vector<int>> dp(1 << m, vector<int>(n + 1)); dp[0][0] = 1; for (int mask = 0; mask < 1 << m; ++mask) for (int i = 0; i < n; ++i) { dp[mask][i + 1] |= dp[mask][i]; for (int cur = mask; cur; cur = (cur - 1) & mask) if (sums[cur] <= cnt[i] && dp[mask ^ cur][i]) dp[mask][i + 1] = 1; } return dp[(1 << m) - 1][n]; } }; |