Distribute repeating integers

Array Hash Table Dynamic Programming Backtracking Bit Manipulation Counting Bitmask

40.5% acceptance

Feb 25, 2026

470

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn can_distribute(nums: Vec<i32>, quantity: Vec<i32>) -> bool {
    use std::collections::HashMap;
    let mut freq_map: HashMap<i32, i32> = HashMap::new();
    for n in nums {
      *freq_map.entry(n).or_insert(0) += 1;
    }
    let mut freq: Vec<i32> = freq_map.values().cloned().collect();
    freq.sort_unstable_by(|a, b| b.cmp(a));

    let m = quantity.len();
    let full = (1usize << m) - 1;

    // Precompute subset sums of quantity
    let mut ss = vec![0i32; 1 << m];
    for s in 1..=(1usize << m) - 1 {
      let lsb = s & s.wrapping_neg();
      let lsb_idx = lsb.trailing_zeros() as usize;
      ss[s] = ss[s ^ lsb] + quantity[lsb_idx];
    }

    // dp[S] = can customers in set S be satisfied using some frequency groups?
    let mut dp = vec![false; 1 << m];
    dp[0] = true;

    for &f in &freq {
      let mut new_dp = dp.clone();
      for s in 1..=full {
        if new_dp[s] {
          continue;
        }
        // Try subsets t of s with ss[t] <= f and dp[s ^ t] true
        let mut t = s;
        while t > 0 {
          if ss[t] <= f && dp[s ^ t] {
            new_dp[s] = true;
            break;
          }
          t = (t - 1) & s;
        }
      }
      dp = new_dp;
      if dp[full] {
        return true;
      }
    }
    dp[full]
  }
}