Distribute Repeating Integers

• Count the frequency of each number in nums and store them in an array or list counts.
• Sort the quantity array in descending order. This is a crucial heuristic to prune the search space by tackling the largest, most restrictive orders first.
• Implement a recursive function, let's call it backtrack(customerIndex, currentCounts).
• Base Case: If customerIndex equals the total number of customers m, it means all customers have been satisfied. Return true.
• For the current customer at customerIndex, get their required quantity.
• Iterate through each available item count in currentCounts.
• If an item count counts[i] is greater than or equal to the required quantity:
  • Tentatively assign this item: counts[i] -= quantity.
  • Make a recursive call for the next customer: backtrack(customerIndex + 1, currentCounts).
  • If the recursive call returns true, a solution has been found, so propagate true upwards.
  • If the call returns false, backtrack by undoing the assignment: counts[i] += quantity.
• If the loop finishes without finding any valid assignment for the current customer, return false.

First, we preprocess the nums array to get the counts of each unique integer. Let's say we have k unique integers with counts c_1, c_2, ..., c_k.

A key optimization is to sort the quantity array in descending order. By trying to satisfy the largest orders first, we can prune the search space more effectively. If a large order cannot be satisfied, we can backtrack early, avoiding the exploration of many dead-end paths.

The core of the approach is a recursive function, say canDistribute(customerIndex). This function tries to find a valid assignment for the customer at customerIndex.

The function iterates through all available unique item counts. If an item count c_i is large enough to satisfy the current customer's quantity q, we tentatively assign it. This means we reduce the count c_i by q and then make a recursive call for the next customer, canDistribute(customerIndex + 1).

If the recursive call returns true, it means a valid distribution was found for the remaining customers, so we propagate true up the call stack.

If the recursive call returns false, we must backtrack. We undo the assignment by adding q back to c_i and then try the next available item count for the current customer.

The base case for the recursion is when customerIndex reaches the total number of customers (m). This signifies that all customers have been successfully satisfied, and we return true.

If the loop over all item counts finishes without finding a valid assignment for the current customer, the function returns false.

1class Solution {2    public boolean canDistribute(int[] nums, int[] quantity) {3        Map<Integer, Integer> countsMap = new HashMap<>();4        for (int num : nums) {5            countsMap.put(num, countsMap.getOrDefault(num, 0) + 1);6        }7        int[] counts = new int[countsMap.size()];8        int i = 0;9        for (int count : countsMap.values()) {10            counts[i++] = count;11        }12        13        // Sort quantity in descending order for pruning14        Arrays.sort(quantity);15        for(int l = 0, r = quantity.length - 1; l < r; l++, r--){16            int temp = quantity[l];17            quantity[l] = quantity[r];18            quantity[r] = temp;19        }20 21        return backtrack(quantity, counts, 0);22    }23 24    private boolean backtrack(int[] quantity, int[] counts, int customerIndex) {25        if (customerIndex == quantity.length) {26            return true;27        }28 29        int currentQuantity = quantity[customerIndex];30        for (int i = 0; i < counts.length; i++) {31            if (counts[i] >= currentQuantity) {32                counts[i] -= currentQuantity;33                if (backtrack(quantity, counts, customerIndex + 1)) {34                    return true;35                }36                counts[i] += currentQuantity; // Backtrack37            }38        }39        return false;40    }41}

• Count the frequency of each number in nums and store them in a list counts of size k.
• Let m = quantity.length.
• Create a subsetSum array of size 2^m. Precompute subsetSum[mask] for all mask from 0 to (1<<m) - 1. subsetSum[mask] is the sum of quantity[i] for all i where the i-th bit of mask is set.
• Create a boolean DP array dp of size 2^m, initialized to false except dp[0] = true (an empty set of customers is always satisfied).
• For each count c in the counts list:
  • Iterate through each mask from (1<<m) - 1 down to 0.
  • If dp[mask] is true (meaning customers in mask can be satisfied with previous items):
    • Find the remainingMask of customers not yet satisfied (~mask).
    • Iterate through all non-empty submasks submask of remainingMask.
    • If subsetSum[submask] <= c, it means the current item count c can satisfy the customers in submask.
    • Update the DP table: dp[mask | submask] = true.
• After all item counts are processed, return dp[(1<<m) - 1], which indicates whether all customers can be satisfied.

First, we preprocess nums to get the counts of unique items, let's call this array counts. We also precompute the sum of quantities for every possible subset of customers. We can use an array subsetSum of size 2^m, where subsetSum[mask] stores the total quantity needed for the customers represented by the bitmask mask. This avoids recalculating these sums inside the main DP loops.

We define a DP array, dp, of size 2^m. dp[mask] will be true if the subset of customers represented by mask can be satisfied, and false otherwise. We initialize dp[0] = true because an empty set of customers requires no items and is trivially satisfied.

The core idea is to build up the dp table by considering one unique item count at a time. For each count c from our counts array, we try to use it to satisfy a new subset of customers, building upon the already satisfiable subsets.

We iterate through each item count c. For each c, we iterate through all masks from (1<<m) - 1 down to 0. The downward iteration is crucial to ensure we use each item count c at most once per state transition. If dp[mask] is true (meaning customers in mask are already satisfied by previous items), we can potentially use the current item c to satisfy a new group of customers.

This new group must be a subset of the currently unsatisfied customers. We can iterate through all submasks submask of the remaining_mask (customers not in mask). If the sum of quantities for submask (subsetSum[submask]) is less than or equal to c, it means we can satisfy this new group. We then update dp[mask | submask] to true.

After iterating through all item counts, the answer to the problem is dp[(1<<m) - 1], which tells us if it's possible to satisfy all m customers.

1class Solution {2    public boolean canDistribute(int[] nums, int[] quantity) {3        Map<Integer, Integer> countsMap = new HashMap<>();4        for (int num : nums) {5            countsMap.put(num, countsMap.getOrDefault(num, 0) + 1);6        }7        List<Integer> counts = new ArrayList<>(countsMap.values());8        int k = counts.size();9        int m = quantity.length;10 11        int[] subsetSum = new int[1 << m];12        for (int i = 0; i < m; i++) {13            for (int mask = 0; mask < (1 << i); mask++) {14                subsetSum[mask | (1 << i)] = subsetSum[mask] + quantity[i];15            }16        }17 18        boolean[] dp = new boolean[1 << m];19        dp[0] = true;20 21        for (int count : counts) {22            for (int mask = (1 << m) - 1; mask >= 0; mask--) {23                if (!dp[mask]) {24                    continue;25                }26                int remainingMask = ((1 << m) - 1) & ~mask;27                for (int submask = remainingMask; submask > 0; submask = (submask - 1) & remainingMask) {28                    if (subsetSum[submask] <= count) {29                        dp[mask | submask] = true;30                    }31                }32            }33        }34 35        return dp[(1 << m) - 1];36    }37}