This page explains Java solution to problem `Distribute Repeating Integers`

using `Backtracking`

algorithm.

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.

Input: nums = [1,2,3,4], quantity = [2]Output: falseExplanation: The 0th customer cannot be given two different integers.

Input: nums = [1,2,3,3], quantity = [2]Output: trueExplanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Input: nums = [1,1,2,2], quantity = [2,2]Output: trueExplanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Input: nums = [1,1,2,3], quantity = [2,2]Output: falseExplanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Input: nums = [1,1,1,1,1], quantity = [2,3]Output: trueExplanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

```
package com.vc.hard;
import java.util.*;
class DistributeRepeatingIntegers {
public boolean canDistribute(int[] nums, int[] quantity) {
HashMap<Integer, Integer> freqMap = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
}
int[] count = new int[freqMap.size()];
int index = 0;
for(int value: freqMap.values()) count[index++] = value;
Arrays.sort(quantity);
return helper(quantity, count, quantity.length - 1);
}
private boolean helper(int[] quantity, int[] count, int qIndex) {
if(qIndex == -1) return true;
for(int i = 0; i < count.length; i++) {
int required = quantity[qIndex];
if(count[i] >= required) {
count[i] -= required;
if(helper(quantity, count, qIndex - 1)) return true;
count[i] += required;
}
}
return false;
}
}
```

O(M

^{N}) Where

M is number of customer orders

N is number of values in an array.

O(M) Where

M is number of customer orders