Problem Description

You are given two integer arrays: nums and quantity.

• nums contains the available numbers, and numbers may repeat.
• quantity represents the number of items each customer wants. There are quantity.length customers, and the i-th customer wants quantity[i] items of any single integer value.

• Each customer gets exactly quantity[i] items, all of the same value.
• No number from nums is reused (each number can only be given once).
• Each customer can receive numbers of any value, but all must be the same for that customer.

• Each customer must be satisfied exactly (no more, no less).
• Each number in nums can only be used once.
• If it is possible to satisfy all customers, return true; otherwise, return false.

Thought Process

The problem asks us to distribute numbers to customers in such a way that each customer receives a specific quantity, and all their items are of the same value. Initially, a brute-force approach might involve trying every possible way to assign numbers to customers, but this would be computationally expensive, especially as the number of customers and types of numbers grows.

Instead, we recognize that the problem is about matching the available counts of each unique number (from nums) to the demands in quantity. Since each customer wants all items to be of the same number, we can think of this as a form of bin-packing or subset assignment problem, where each bin is a unique number and the items to pack are the customer requests.

The challenge is to efficiently check if there is a way to assign customer requests to available number counts without overlap, and without trying every possible permutation explicitly.

Solution Approach

To solve the problem efficiently, we use a recursive backtracking algorithm with memoization. Here are the key steps:

1. Count the frequency of each unique number in nums using a hash map. This tells us how many times each number is available to distribute.
2. Sort the quantity array in descending order. This helps us try to satisfy the largest requests first, which often leads to faster pruning in backtracking.
3. Define a recursive function that tries to assign each customer's request to a unique number's available count. For each customer, we iterate over all unique numbers and, if that number's count is enough, we assign it and recurse to the next customer.
4. Memoize the state of the recursion using the current index in quantity and the current counts of all numbers. This prevents recalculating the same state multiple times.
5. Base case: If all customers have been satisfied, return true. If not, try all possible assignments; if none work, return false.

We use memoization (caching) to avoid redundant calculations, and by always trying the largest requests first, we minimize unnecessary work early.

Example Walkthrough

Suppose nums = [1,1,2,2,3,3] and quantity = [2,2,2].

• We count: There are 2 of each number (1, 2, and 3).
• We sort quantity: Already [2,2,2].
• Try to assign the first customer (needs 2) to number 1 (has 2): assign, decrement count for 1 to 0.
• Next customer (needs 2): Try number 2 (has 2): assign, decrement count for 2 to 0.
• Last customer (needs 2): Try number 3 (has 2): assign, decrement count for 3 to 0.
• All customers are satisfied and no counts went negative, so return true.
• If at any point no number has enough remaining for a customer, backtrack and try a different assignment.

Time and Space Complexity

Brute-force approach: Would try all possible assignments of customer requests to numbers, leading to a time complexity of O(k^n), where k is the number of unique numbers and n is the number of customers. This is not feasible for large inputs.

Optimized approach (backtracking with memoization): The total number of states is bounded by the number of possible combinations of customer indices and the state of the counts (which is exponential in the number of unique numbers, but manageable due to memoization and pruning). In practice, this is much faster than brute-force, especially with small quantity arrays (usually ≤10).

Space complexity: O(m + n * 2^n), where m is the number of unique numbers (for the counts), and 2^n is for the memoization table (since we can represent the assignment of customers as a bitmask).

Summary

The key insight is to model the problem as assigning customer requests to available number counts, ensuring no overlap and that each customer gets their exact request. By using backtracking with memoization and smart ordering (largest requests first), we efficiently explore the solution space and avoid redundant work. This approach makes it possible to solve what would otherwise be a computationally intractable problem.

Code Implementation

from collections import Counter
from functools import lru_cache

class Solution:
    def canDistribute(self, nums, quantity):
        count = list(Counter(nums).values())
        quantity.sort(reverse=True)
        n = len(quantity)
        m = len(count)
        
        @lru_cache(maxsize=None)
        def dfs(i, mask):
            if mask == 0:
                return True
            if i == m:
                return False
            sub = mask
            while sub:
                need = 0
                idx = []
                for j in range(n):
                    if (sub >> j) & 1:
                        need += quantity[j]
                        idx.append(j)
                if need <= count[i]:
                    if dfs(i + 1, mask ^ sub):
                        return True
                sub = (sub - 1) & mask
            if dfs(i + 1, mask):
                return True
            return False
        
        return dfs(0, (1 << n) - 1)
      

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        vector<int> counts;
        for (auto &p : freq) counts.push_back(p.second);
        sort(quantity.rbegin(), quantity.rend());
        int m = counts.size(), n = quantity.size();
        vector<vector<int>> memo(m + 1, vector<int>(1 << n, -1));
        function<bool(int, int)> dfs = [&](int i, int mask) {
            if (mask == 0) return true;
            if (i == m) return false;
            if (memo[i][mask] != -1) return memo[i][mask];
            int sub = mask;
            while (sub) {
                int need = 0;
                for (int j = 0; j < n; ++j)
                    if ((sub >> j) & 1) need += quantity[j];
                if (need <= counts[i] && dfs(i + 1, mask ^ sub))
                    return memo[i][mask] = true;
                sub = (sub - 1) & mask;
            }
            if (dfs(i + 1, mask)) return memo[i][mask] = true;
            return memo[i][mask] = false;
        };
        return dfs(0, (1 << n) - 1);
    }
};
      

import java.util.*;

class Solution {
    public boolean canDistribute(int[] nums, int[] quantity) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int[] counts = new int[freq.size()];
        int idx = 0;
        for (int v : freq.values()) counts[idx++] = v;
        Arrays.sort(quantity);
        for (int i = 0, j = quantity.length - 1; i < j; i++, j--) {
            int tmp = quantity[i]; quantity[i] = quantity[j]; quantity[j] = tmp;
        }
        int m = counts.length, n = quantity.length;
        Boolean[][] memo = new Boolean[m + 1][1 << n];
        return dfs(0, (1 << n) - 1, counts, quantity, memo);
    }
    
    private boolean dfs(int i, int mask, int[] counts, int[] quantity, Boolean[][] memo) {
        if (mask == 0) return true;
        if (i == counts.length) return false;
        if (memo[i][mask] != null) return memo[i][mask];
        int sub = mask;
        while (sub != 0) {
            int need = 0;
            for (int j = 0; j < quantity.length; ++j)
                if (((sub >> j) & 1) == 1) need += quantity[j];
            if (need <= counts[i] && dfs(i + 1, mask ^ sub, counts, quantity, memo)) {
                memo[i][mask] = true;
                return true;
            }
            sub = (sub - 1) & mask;
        }
        if (dfs(i + 1, mask, counts, quantity, memo)) {
            memo[i][mask] = true;
            return true;
        }
        memo[i][mask] = false;
        return false;
    }
}
      

var canDistribute = function(nums, quantity) {
    const freq = {};
    for (const x of nums) freq[x] = (freq[x] || 0) + 1;
    const counts = Object.values(freq);
    quantity.sort((a, b) => b - a);
    const m = counts.length, n = quantity.length;
    const memo = Array.from({length: m + 1}, () => ({}));
    function dfs(i, mask) {
        if (mask === 0) return true;
        if (i === m) return false;
        if (memo[i][mask] !== undefined) return memo[i][mask];
        let sub = mask;
        while (sub) {
            let need = 0;
            for (let j = 0; j < n; ++j)
                if ((sub >> j) & 1) need += quantity[j];
            if (need <= counts[i] && dfs(i + 1, mask ^ sub)) {
                memo[i][mask] = true;
                return true;
            }
            sub = (sub - 1) & mask;
        }
        if (dfs(i + 1, mask)) {
            memo[i][mask] = true;
            return true;
        }
        memo[i][mask] = false;
        return false;
    }
    return dfs(0, (1 << n) - 1);
};