1681. Minimum Incompatibility

• Time: $O(3^n)$
• Space: $O(2^n)$

C++JavaPython

class Solution {
 public:
  int minimumIncompatibility(vector<int>& nums, int k) {
    constexpr int kMaxCompatibility = (16 - 1) * (16 / 2);
    const int n = nums.size();
    const int subsetSize = n / k;
    const int maxMask = 1 << n;
    const vector<int> incompatibilities =
        getIncompatibilities(nums, subsetSize);
    // dp[i] := the minimum possible sum of incompatibilities of the subset
    // of numbers represented by the bitmask i
    vector<int> dp(maxMask, kMaxCompatibility);
    dp[0] = 0;

    for (unsigned mask = 1; mask < maxMask; ++mask) {
      // The number of 1s in `mask` isn't a multiple of `subsetSize`.
      if (popcount(mask) % subsetSize != 0)
        continue;
      // https://cp-algorithms.com/algebra/all-submasks.html
      for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
        if (incompatibilities[submask] != -1)  // valid subset
          dp[mask] =
              min(dp[mask], dp[mask - submask] + incompatibilities[submask]);
    }

    return dp.back() == kMaxCompatibility ? -1 : dp.back();
  }

 private:
  static constexpr int kMaxNum = 16;

  // Returns an incompatibilities array where
  // * incompatibilities[i] := the incompatibility of the subset of numbers
  //   represented by the bitmask i
  // * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
  //   `subsetSize`
  vector<int> getIncompatibilities(const vector<int>& nums, int subsetSize) {
    const int maxMask = 1 << nums.size();
    vector<int> incompatibilities(maxMask, -1);
    for (unsigned mask = 0; mask < maxMask; ++mask)
      if (popcount(mask) == subsetSize && isUnique(nums, mask, subsetSize))
        incompatibilities[mask] = getIncompatibility(nums, mask);
    return incompatibilities;
  }

  // Returns true if the numbers selected by `mask` are unique.
  //
  // e.g. If we call isUnique(0b1010, 2, [1, 2, 1, 4]), `used` variable
  // will be 0b1, which only has one 1 (less than `subsetSize`). In this case,
  // we should return false.
  bool isUnique(const vector<int>& nums, int mask, int subsetSize) {
    unsigned used = 0;
    for (int i = 0; i < nums.size(); ++i)
      if (mask >> i & 1)
        used |= 1 << nums[i];
    return popcount(used) == subsetSize;
  }

  // Returns the incompatibility of the selected numbers represented by the
  // `mask`.
  int getIncompatibility(const vector<int>& nums, int mask) {
    int mn = kMaxNum;
    int mx = 0;
    for (int i = 0; i < nums.size(); ++i)
      if (mask >> i & 1) {
        mx = max(mx, nums[i]);
        mn = min(mn, nums[i]);
      }
    return mx - mn;
  }
};

class Solution {
  public int minimumIncompatibility(int[] nums, int k) {
    final int kMaxCompatibility = (16 - 1) * (16 / 2);
    final int n = nums.length;
    final int subsetSize = n / k;
    final int maxMask = 1 << n;
    final int[] incompatibilities = getIncompatibilities(nums, subsetSize);
    // dp[i] := the minimum possible sum of incompatibilities of the subset
    // of numbers represented by the bitmask i
    int[] dp = new int[maxMask];
    Arrays.fill(dp, kMaxCompatibility);
    dp[0] = 0;

    for (int mask = 1; mask < maxMask; ++mask) {
      // The number of 1s in `mask` isn't a multiple of `subsetSize`.
      if (Integer.bitCount(mask) % subsetSize != 0)
        continue;
      // https://cp-algorithms.com/algebra/all-submasks.html
      for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
        if (incompatibilities[submask] != -1) // valid submask
          dp[mask] = Math.min(dp[mask], dp[mask - submask] + incompatibilities[submask]);
    }

    return dp[maxMask - 1] == kMaxCompatibility ? -1 : dp[maxMask - 1];
  }

  private static final int kMaxNum = 16;

  // Returns an incompatibilities array where
  // * incompatibilities[i] := the incompatibility of the subset of numbers
  //   represented by the bitmask i
  // * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
  //   `subsetSize`
  private int[] getIncompatibilities(int[] nums, int subsetSize) {
    final int maxMask = 1 << nums.length;
    int[] incompatibilities = new int[maxMask];
    Arrays.fill(incompatibilities, -1);
    for (int mask = 0; mask < maxMask; ++mask)
      if (Integer.bitCount(mask) == subsetSize && isUnique(nums, mask, subsetSize))
        incompatibilities[mask] = getIncompatibility(nums, mask);
    return incompatibilities;
  }

  // Returns true if the numbers selected by `mask` are unique.
  //
  // e.g. If we call isUnique(0b1010, 2, [1, 2, 1, 4]), `used` variable
  // will be 0b1, which only has one 1 (less than `subsetSize`). In this case,
  // we should return false.
  private boolean isUnique(int[] nums, int mask, int subsetSize) {
    int used = 0;
    for (int i = 0; i < nums.length; ++i)
      if ((mask >> i & 1) == 1)
        used |= 1 << nums[i];
    return Integer.bitCount(used) == subsetSize;
  }

  // Returns the incompatibility of the selected numbers represented by the
  // `mask`.
  private int getIncompatibility(int[] nums, int mask) {
    int mn = kMaxNum;
    int mx = 0;
    for (int i = 0; i < nums.length; ++i)
      if ((mask >> i & 1) == 1) {
        mx = Math.max(mx, nums[i]);
        mn = Math.min(mn, nums[i]);
      }
    return mx - mn;
  }
}

class Solution:
  def __init__(self):
    self.kMaxNum = 16

  def minimumIncompatibility(self, nums: list[int], k: int) -> int:
    kMaxCompatibility = (16 - 1) * (16 // 2)
    n = len(nums)
    subsetSize = n // k
    maxMask = 1 << n
    incompatibilities = self._getIncompatibilities(nums, subsetSize)

    # dp[i] := the minimum possible sum of incompatibilities of the subset
    # of numbers represented by the bitmask i
    dp = [kMaxCompatibility] * maxMask
    dp[0] = 0

    for mask in range(1, maxMask):
      # The number of 1s in `mask` isn't a multiple of `subsetSize`.
      if mask.bit_count() % subsetSize != 0:
        continue
      # https://cp-algorithms.com/algebra/all-submasks.html
      submask = mask
      while submask > 0:
        if incompatibilities[submask] != -1:  # valid submask
          dp[mask] = min(dp[mask], dp[mask - submask] +
                         incompatibilities[submask])
        submask = (submask - 1) & mask

    return dp[-1] if dp[-1] != kMaxCompatibility else -1

  def _getIncompatibilities(
      self,
      nums: list[int],
      subsetSize: int,
  ) -> list[int]:
    """
    Returns an incompatibilities array where
    * incompatibilities[i] := the incompatibility of the subset of numbers
      represented by the bitmask i
    * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not
      `subsetSize`
    """
    maxMask = 1 << len(nums)
    incompatibilities = [-1] * maxMask
    for mask in range(maxMask):
      if mask.bit_count() == subsetSize and self._isUnique(nums, mask, subsetSize):
        incompatibilities[mask] = self._getIncompatibility(nums, mask)
    return incompatibilities

  def _isUnique(self, nums: list[int], mask: int, subsetSize: int) -> bool:
    """Returns True if the numbers selected by `mask` are unique."""
    used = 0
    for i, num in enumerate(nums):
      if mask >> i & 1:
        used |= 1 << num
    return used.bit_count() == subsetSize

  def _getIncompatibility(self, nums: list[int], mask: int) -> int:
    """
    Returns the incompatibility of the selected numbers represented by the
    `mask`.
    """
    mn = self.kMaxNum
    mx = 0
    for i, num in enumerate(nums):
      if mask >> i & 1:
        mx = max(mx, num)
        mn = min(mn, num)
    return mx - mn