# Distribute Repeating Integers
**Difficulty:** HARD
[External](https://leetcode.com/problems/distribute-repeating-integers)
Canonical: https://scaleengineer.com/dsa/problems/distribute-repeating-integers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## Problem
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 **exactly** `quantity[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`.

# Approaches
## Backtracking with Pruning
This approach attempts to solve the problem by trying every possible assignment of items to customers. It uses a recursive depth-first search (DFS) to explore the solution space. We try to satisfy each customer one by one. To make the search more efficient, we apply a pruning heuristic: we sort the customer quantities in descending order and try to satisfy the largest orders first. This helps to fail faster and cut off large branches of the search tree that are not promising.
**Time:** O(k^m), where `k` is the number of unique integers (at most 50) and `m` is the number of customers (at most 10). In the worst case, for each of the `m` customers, we might try all `k` available item counts. While sorting `quantity` provides some pruning, the worst-case complexity remains exponential and is too slow for the given constraints. · **Space:** O(m + k), where `m` is the number of customers and `k` is the number of unique items. This is for the recursion stack depth (`O(m)`) and to store the item counts (`O(k)`).
**Pros:** Relatively simple to understand and implement.; The logic directly models the problem of assigning items to customers.
**Cons:** The worst-case time complexity is prohibitively high for the given constraints, leading to a 'Time Limit Exceeded' (TLE) error on many test cases.; It recomputes solutions for the same subproblems repeatedly, as it lacks memoization.
### Explanation
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`.

```java
class Solution {
    public boolean canDistribute(int[] nums, int[] quantity) {
        Map<Integer, Integer> countsMap = new HashMap<>();
        for (int num : nums) {
            countsMap.put(num, countsMap.getOrDefault(num, 0) + 1);
        }
        int[] counts = new int[countsMap.size()];
        int i = 0;
        for (int count : countsMap.values()) {
            counts[i++] = count;
        }
        
        // Sort quantity in descending order for pruning
        Arrays.sort(quantity);
        for(int l = 0, r = quantity.length - 1; l < r; l++, r--){
            int temp = quantity[l];
            quantity[l] = quantity[r];
            quantity[r] = temp;
        }

        return backtrack(quantity, counts, 0);
    }

    private boolean backtrack(int[] quantity, int[] counts, int customerIndex) {
        if (customerIndex == quantity.length) {
            return true;
        }

        int currentQuantity = quantity[customerIndex];
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] >= currentQuantity) {
                counts[i] -= currentQuantity;
                if (backtrack(quantity, counts, customerIndex + 1)) {
                    return true;
                }
                counts[i] += currentQuantity; // Backtrack
            }
        }
        return false;
    }
}
```
### Algorithm
- 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`.

## Dynamic Programming with Bitmasking
This approach reframes the problem to be solvable with dynamic programming. Since the number of customers `m` is small (up to 10), we can use a bitmask of length `m` to represent any subset of customers. The state of our DP will be based on which subset of customers has been satisfied. We build up a solution by iterating through each available stock of a unique item and determining which new subsets of customers can be satisfied.
**Time:** O(k * 3^m + m * 2^m). The `subsetSum` precomputation takes `O(m * 2^m)`. The main DP calculation involves an outer loop of size `k` (item counts). The two inner loops (over `mask` and `submask`) result in a complexity of `O(3^m)` per item count. With `k <= 50` and `m <= 10`, this is highly efficient. · **Space:** O(2^m + k), where `m` is the number of customers and `k` is the number of unique items. `O(2^m)` is required for the `dp` and `subsetSum` arrays, and `O(k)` for storing the item counts.
**Pros:** Guaranteed to find the correct solution.; Efficient enough to pass within the time limits for the given constraints.; Avoids recomputing results for subproblems by storing them in the DP table.
**Cons:** The logic is more complex and less intuitive than the straightforward backtracking approach.; The space complexity is exponential in `m`, which could be an issue if `m` were larger.
### Explanation
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.

```java
class Solution {
    public boolean canDistribute(int[] nums, int[] quantity) {
        Map<Integer, Integer> countsMap = new HashMap<>();
        for (int num : nums) {
            countsMap.put(num, countsMap.getOrDefault(num, 0) + 1);
        }
        List<Integer> counts = new ArrayList<>(countsMap.values());
        int k = counts.size();
        int m = quantity.length;

        int[] subsetSum = new int[1 << m];
        for (int i = 0; i < m; i++) {
            for (int mask = 0; mask < (1 << i); mask++) {
                subsetSum[mask | (1 << i)] = subsetSum[mask] + quantity[i];
            }
        }

        boolean[] dp = new boolean[1 << m];
        dp[0] = true;

        for (int count : counts) {
            for (int mask = (1 << m) - 1; mask >= 0; mask--) {
                if (!dp[mask]) {
                    continue;
                }
                int remainingMask = ((1 << m) - 1) & ~mask;
                for (int submask = remainingMask; submask > 0; submask = (submask - 1) & remainingMask) {
                    if (subsetSum[submask] <= count) {
                        dp[mask | submask] = true;
                    }
                }
            }
        }

        return dp[(1 << m) - 1];
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
class Solution {
public
  boolean canDistribute(int[] nums, int[] quantity) {
    int m = quantity.length;
    int[] s = new int[1 << m];
    for (int i = 1; i < 1 << m; ++i) {
      for (int j = 0; j < m; ++j) {
        if ((i >> j & 1) != 0) {
          s[i] = s[i ^ (1 << j)] + quantity[j];
          break;
        }
      }
    }
    Map<Integer, Integer> cnt = new HashMap<>(50);
    for (int x : nums) {
      cnt.merge(x, 1, Integer : : sum);
    }
    int n = cnt.size();
    int[] arr = new int[n];
    int i = 0;
    for (int x : cnt.values()) {
      arr[i++] = x;
    }
    boolean[][] f = new boolean[n][1 << m];
    for (i = 0; i < n; ++i) {
      f[i][0] = true;
    }
    for (i = 0; i < n; ++i) {
      for (int j = 1; j < 1 << m; ++j) {
        if (i > 0 && f[i - 1][j]) {
          f[i][j] = true;
          continue;
        }
        for (int k = j; k > 0; k = (k - 1) & j) {
          boolean ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
          boolean ok2 = s[k] <= arr[i];
          if (ok1 && ok2) {
            f[i][j] = true;
            break;
          }
        }
      }
    }
    return f[n - 1][(1 << m) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canDistribute(vector<int> &nums, vector<int> &quantity) {
    int m = quantity.size();
    int s[1 << m];
    memset(s, 0, sizeof(s));
    for (int i = 1; i < 1 << m; ++i) {
      for (int j = 0; j < m; ++j) {
        if (i >> j & 1) {
          s[i] = s[i ^ (1 << j)] + quantity[j];
          break;
        }
      }
    }
    unordered_map<int, int> cnt;
    for (int &x : nums) {
      ++cnt[x];
    }
    int n = cnt.size();
    vector<int> arr;
    for (auto &[_, x] : cnt) {
      arr.push_back(x);
    }
    bool f[n][1 << m];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[i][0] = true;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 1; j < 1 << m; ++j) {
        if (i && f[i - 1][j]) {
          f[i][j] = true;
          continue;
        }
        for (int k = j; k; k = (k - 1) & j) {
          bool ok1 = i == 0 ? j == k : f[i - 1][j ^ k];
          bool ok2 = s[k] <= arr[i];
          if (ok1 && ok2) {
            f[i][j] = true;
            break;
          }
        }
      }
    }
    return f[n - 1][(1 << m) - 1];
  }
};

```

### Python

```python
class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool: m = len(quantity) s = [0] * (1 << m) for i in range(1, 1 << m): for j in range(m): if i >> j & 1: s[i] = s[i ^ (1 << j)] + quantity[j] break cnt = Counter(nums) arr = list(cnt . values()) n = len(arr) f = [[False] * (1 << m) for _ in range(n)] for i in range(n): f[i][0] = True for i, x in enumerate(arr): for j in range(1, 1 << m): if i and f[i - 1][j]: f[i][j] = True continue k = j while k: ok1 = j == k if i == 0 else f[i - 1][j ^ k] ok2 = s[k] <= x if ok1 and ok2: f[i][j] = True break k = (k - 1) & j return f[- 1][- 1]

```