Formatted question description: https://leetcode.ca/all/1655.html

# 1655. Distribute Repeating Integers

## Level

Hard

## Description

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 `i-th`

customer ordered. Determine if it is possible to distribute `nums`

such that:

- The
`i-th`

customer gets exactly`quantity[i]`

integers, - The integers the
`i-th`

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 <= 10^5`

`1 <= nums[i] <= 1000`

`m == quantity.length`

`1 <= m <= 10`

`1 <= quantity[i] <= 10^5`

- There are at most
`50`

unique values in`nums`

.

## Solution

First, use a map to store all numbers’ occurrences in `nums`

. Then sort `quantity`

, and do backtrack using the map and `quantity`

, from the last element of `quantity`

.

During the backtrack, if an entry’s value is greater than or equal to the current value of `quantity`

, then try to distribute the integers to a customer, and continue the process for the next customer. If all customers are satisfied, return `true`

. If there is no way to make all customers satisfied, return `false`

.

```
class Solution {
public boolean canDistribute(int[] nums, int[] quantity) {
int sum = 0;
for (int num : quantity)
sum += num;
if (sum > nums.length)
return false;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
Arrays.sort(quantity);
return backtrack(map, quantity, quantity.length - 1);
}
public boolean backtrack(Map<Integer, Integer> map, int[] quantity, int index) {
if (index == -1)
return true;
boolean flag = false;
int curQuantity = quantity[index];
Set<Integer> keySet = map.keySet();
for (int key : keySet) {
int value = map.get(key);
if (value >= curQuantity) {
map.put(key, value - curQuantity);
flag = backtrack(map, quantity, index - 1);
if (flag)
break;
else
map.put(key, value);
}
}
return flag;
}
}
```