https://leetcode.com/problems/distribute-repeating-integers/ from Google

Thinking process:

Look at the constraint. Look like we need to start from quantity. One way to do this is to just use recursion and backtracking. We can handle customers one by one until either we can’t handle anymore or we complete all of them. This sounds like a O(50^10) algorithem, so I didn’t go try this.

Another way to think of this is to count the count of each integer first (the freq array I use below). With this, we can use those counts one by one, and see how many customers can be happy (order is satisfied) with those counts.

Since the customer size is only 10, we can use a bit map to represent those customers already being happy. In my code, I count the freq first, and then create a sq to pre-compute the sum of quantity we need for each bit map.

After that, I create another 2-D boolean array dp. We use i to mean the number of freq we already use to satisfy customers’ orders. We use j to mean the bit map of customers already being happy, and k to mean the new customers we want to serve, so j&k should be 0 as we don’t want to serve customers twice, and if sq[k] is equal or less than the current freq, we can serve this new set of customers.

Below is the code. The time complextiy will be O(50 * 1024 * 1024), which is about 5*10^7. I thought I would get TLE for this, but looks like it’s okay.

 1class Solution {
 2public:
 3    bool canDistribute(vector<int>& nums, vector<int>& q) {
 4        int N = q.size();
 5        unordered_map<int, int> mp;
 6        for (auto n : nums) {
 7            mp[n]++;
 8        }
 9        vector<int> freq;
10        for (auto p : mp) {
11            freq.push_back(p.second);
12        }
13        int LF = freq.size();
14        vector<int> sq(1<<N); // sum of quantity
15        for (int i=0; i<(1<<N); i++) {
16            for (int j=0; j<N; j++) {
17                if (i & (1<<j)) {
18                    sq[i] += q[j];
19                }
20            }
21        }
22        vector<vector<bool>> dp(LF+1, vector<bool>(1<<N));
23        dp[0][0] = true;
24        for (int i=1; i<=LF; i++) {
25            for (int j=0; j<(1<<N); j++) {
26                if (!dp[i-1][j]) continue;
27                for (int k=0; k<(1<<N); k++) {
28                    if (k & j) continue;
29                    if (sq[k] > freq[i-1]) continue;
30                    dp[i][k|j] = true;
31                }
32            }
33        }
34        return dp[LF][(1<<N)-1];
35    }
36};