动态规划 + 状态压缩 + bitCount 统计二进制 1 个数，求解《1681. 最小不兼容性》

substr_count(decbin($mask), '1')

bits.OnesCount(uint(mask))

Integer.bitCount(mask)

BitOperations.PopCount((uint)mask)

__builtin_popcount(mask)

__builtin_popcount(mask)

# python3 only
mask.bit_count()

# python2
def bitCount(self, n):
    cnt = 0
    while n > 0:
      cnt += 1
      n &= n - 1
    return cnt

const bitCount = n => {
  let cnt = 0
  while (n > 0) {
    cnt++
    n &= n - 1
  }
  return cnt
}

var minimumIncompatibility = function(nums, k) {
  const n  = nums.length, dp = new Array(1 << n).fill(Number.MAX_SAFE_INTEGER)
  const incompatibilities = new Array(1 << n), average = n / k
  label: for (let mask = 0; mask < 1 << n; mask++) {
    if (bitCount(mask) !== average) continue
    const groupSet = new Set
    let maxNum = 0, minNum = n + 1
    for (let i = 0; i < n; i++) {
      if ((mask & 1 << i) === 0) continue
      if (groupSet.has(nums[i])) continue label
      groupSet.add(nums[i])
      if (maxNum < nums[i]) maxNum = nums[i]
      if (minNum > nums[i]) minNum = nums[i]
    }
    if (groupSet.size === average) incompatibilities[mask] = maxNum - minNum
  }
  dp[0] = 0
  for (let mask = 0; mask < 1 << n; mask++) {
    if (dp[mask] === Number.MAX_SAFE_INTEGER) continue
    const remainMap = new Map
    for (let i = 0; i < n; i++) {
      if ((mask & 1 << i) >= 1) continue
      remainMap.set(nums[i], i)
    }
    if (remainMap.size < average) continue
    let remainMask = 0
    for (const i of remainMap.values()) remainMask |= (1 << i)
    for (let sub = remainMask; sub > 0; sub = remainMask & (sub - 1)) {
      if (incompatibilities[sub] !== void 0) dp[mask | sub] = Math.min(dp[mask | sub], dp[mask] + incompatibilities[sub])
    }
  }
  return dp[(1 << n) - 1] === Number.MAX_SAFE_INTEGER ? -1 : dp[(1 << n) - 1]
};

const bitCount = n => {
  let cnt = 0
  while (n > 0) {
    cnt++
    n &= n - 1
  }
  return cnt
}

function minimumIncompatibility(nums: number[], k: number): number {
  const n  = nums.length, dp = new Array(1 << n).fill(Number.MAX_SAFE_INTEGER)
  const incompatibilities = new Array(1 << n), average = n / k
  label: for (let mask = 0; mask < 1 << n; mask++) {
    if (bitCount(mask) !== average) continue
    const groupSet = new Set
    let maxNum = 0, minNum = n + 1
    for (let i = 0; i < n; i++) {
      if ((mask & 1 << i) === 0) continue
      if (groupSet.has(nums[i])) continue label
      groupSet.add(nums[i])
      if (maxNum < nums[i]) maxNum = nums[i]
      if (minNum > nums[i]) minNum = nums[i]
    }
    if (groupSet.size === average) incompatibilities[mask] = maxNum - minNum
  }
  dp[0] = 0
  for (let mask = 0; mask < 1 << n; mask++) {
    if (dp[mask] === Number.MAX_SAFE_INTEGER) continue
    const remainMap = new Map
    for (let i = 0; i < n; i++) {
      if ((mask & 1 << i) >= 1) continue
      remainMap.set(nums[i], i)
    }
    if (remainMap.size < average) continue
    let remainMask = 0
    for (const i of remainMap.values()) remainMask |= (1 << i)
    for (let sub = remainMask; sub > 0; sub = remainMask & (sub - 1)) {
      if (incompatibilities[sub] !== void 0) dp[mask | sub] = Math.min(dp[mask | sub], dp[mask] + incompatibilities[sub])
    }
  }
  return dp[(1 << n) - 1] === Number.MAX_SAFE_INTEGER ? -1 : dp[(1 << n) - 1]
};

const bitCount = (n: number): number => {
  let cnt = 0
  while (n > 0) {
    cnt++
    n &= n - 1
  }
  return cnt
}

function minimumIncompatibility($nums, $k) {
    $n = count($nums);
    $dp = array_fill(0, 1 << $n, PHP_INT_MAX);
    $incompatibilities = array_fill(0, 1 << $n, null);
    $average = $n / $k;

    for ($mask = 0; $mask < (1 << $n); $mask++) {
        if (substr_count(decbin($mask), '1') !== $average) continue;
        $groupSet = array();
        $maxNum = 0;
        $minNum = $n + 1;
        for ($i = 0; $i < $n; $i++) {
            if (($mask & (1 << $i)) === 0) continue;
            if (in_array($nums[$i], $groupSet)) break;
            array_push($groupSet, $nums[$i]);
            if ($maxNum < $nums[$i]) $maxNum = $nums[$i];
            if ($minNum > $nums[$i]) $minNum = $nums[$i];
        }
        if (count($groupSet) === $average) $incompatibilities[$mask] = $maxNum - $minNum;
    }

    $dp[0] = 0;
    for ($mask = 0; $mask < (1 << $n); $mask++) {
        if ($dp[$mask] === PHP_INT_MAX) continue;
        $remainMap = array();
        for ($i = 0; $i < $n; $i++) {
            if (($mask & (1 << $i)) >= 1) continue;
            $remainMap[$nums[$i]] = $i;
        }
        if (count($remainMap) < $average) continue;
        $remainMask = 0;
        foreach ($remainMap as $i) {
            $remainMask |= (1 << $i);
        }
        for ($sub = $remainMask; $sub > 0; $sub = $remainMask & ($sub - 1)) {
            if ($incompatibilities[$sub] !== null) {
                $dp[$mask | $sub] = min($dp[$mask | $sub], $dp[$mask] + $incompatibilities[$sub]);
            }
        }
    }

    return $dp[(1 << $n) - 1] === PHP_INT_MAX ? -1 : $dp[(1 << $n) - 1];
}

func minimumIncompatibility(nums []int, k int) int {
  n, intMax := len(nums), int(^uint(0) >> 1)
  dp, average := make([]int, 1 << n), n / k
  incompatibilities := map[int]int{}
  for mask := 0; mask < 1 << n; mask++ {
    dp[mask] = intMax
    if bits.OnesCount(uint(mask)) != average {
      continue
    }
    groupSet, minNum, maxNum := map[int]struct{}{}, n + 1, 0
    for i := 0; i < n; i++ {
      if (mask & (1 << i)) == 0 {
        continue
      }
      if _, ok := groupSet[nums[i]]; ok == true {
        break
      }
      groupSet[nums[i]] = struct{}{}
      if maxNum < nums[i] {
        maxNum = nums[i]
      }
      if minNum > nums[i] {
        minNum = nums[i]
      }
    }
    if len(groupSet) == average {
      incompatibilities[mask] = maxNum - minNum
    }
  }
  dp[0] = 0
  for mask := 0; mask < 1 << n; mask++ {
    if dp[mask] == intMax {
      continue
    }
    remainMap := map[int]int{}
    for i := 0; i < n; i++ {
      if (mask & (1 << i)) >= 1 {
        continue
      }
      remainMap[nums[i]] = i
    }
    remainMask := 0
    for _, i := range remainMap {
      remainMask |= 1 << i
    }
    for sub := remainMask; sub > 0; sub = remainMask & (sub - 1) {
      if _, ok := incompatibilities[sub]; ok == false {
        continue
      }
      dp[mask | sub] = min(dp[mask | sub], dp[mask] + incompatibilities[sub])
    }
  }
  if dp[1 << n - 1] == intMax {
    return -1
  }
  return  dp[1 << n - 1]
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

class Solution {
  public int minimumIncompatibility(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[1 << n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    int average = n / k;
    HashMap<Integer, Integer> incompatibilities = new HashMap<Integer, Integer>();
    label: for (int mask = 0; mask < 1 << n; mask++) {
      if (Integer.bitCount(mask) != average) continue;
      HashSet<Integer> groupSet = new HashSet<Integer>();
      int minNum = n + 1, maxNum = 0;
      for (int i = 0; i < n; i++) {
        if ((mask & 1 << i) == 0) continue;
        if (groupSet.contains(nums[i])) continue label;
        groupSet.add(nums[i]);
        if (minNum > nums[i]) minNum = nums[i];
        if (maxNum < nums[i]) maxNum = nums[i];

      }
      incompatibilities.put(mask, maxNum - minNum);
    }
    dp[0] = 0;
    for (int mask = 0; mask < 1 << n; mask++) {
      if (dp[mask] == Integer.MAX_VALUE) continue;
      HashMap<Integer, Integer> remainMap = new HashMap<Integer, Integer>();
      for (int i = 0; i < n; i++) {
        if ((mask & 1 << i) >= 1) continue;
        remainMap.put(nums[i], i);
      }
      if (remainMap.size() < average) continue;
      int remainMask = 0;
      for (int i : remainMap.values()) {
        remainMask |= 1 << i;
      }
      for (int sub = remainMask; sub > 0; sub = remainMask & (sub - 1)) {
        if (incompatibilities.containsKey(sub) == false) continue;
        dp[mask | sub] = Math.min(dp[mask | sub], dp[mask] + incompatibilities.get(sub));
      }
    }
    return dp[(1 << n) - 1] == Integer.MAX_VALUE ? -1 : dp[(1 << n) - 1]; 
  }
}

public class Solution {
  public int MinimumIncompatibility(int[] nums, int k) {
    int n = nums.Length;
    int[] dp = new int[1 << n];
    Array.Fill(dp, int.MaxValue);
    int average = n / k;
    Dictionary<int, int> incompatibilities = new Dictionary<int, int>();
    for (int mask = 0; mask < 1 << n; mask++) {
      if (BitOperations.PopCount((uint)mask) != average) continue;
      ISet<int> groupSet = new HashSet<int>();
      int minNum = n + 1, maxNum = 0;
      for (int i = 0; i < n; i++) {
        if ((mask & 1 << i) == 0) continue;
        if (groupSet.Contains(nums[i])) break;
        groupSet.Add(nums[i]);
        if (minNum > nums[i]) minNum = nums[i];
        if (maxNum < nums[i]) maxNum = nums[i];
      }
      if (groupSet.Count == average) incompatibilities.TryAdd(mask, maxNum - minNum);
    }
    dp[0] = 0;
    for (int mask = 0; mask < 1 << n; mask++) {
      if (dp[mask] == int.MaxValue) continue;
      Dictionary<int, int> remainMap = new Dictionary<int, int>();
      for (int i = 0; i < n; i++) {
        if ((mask & 1 << i) >= 1) continue;
        remainMap.TryAdd(nums[i], i);
      }
      if (remainMap.Count < average) continue;
      int remainMask = 0;
      foreach (int i in remainMap.Values) {
        remainMask |= 1 << i;
      }
      for (int sub = remainMask; sub > 0; sub = remainMask & (sub - 1)) {
        if (incompatibilities.ContainsKey(sub) == false) continue;
        dp[mask | sub] = Math.Min(dp[mask | sub], dp[mask] + incompatibilities[sub]);
      }
    }
    return dp[(1 << n) - 1] == int.MaxValue ? -1 : dp[(1 << n) - 1]; 
  }
}

class Solution {
public:
  int minimumIncompatibility(vector<int>& nums, int k) {
    int n = nums.size(), average = n / k;
    vector<int> dp(1 << n, INT_MAX);
    unordered_map<int, int> incompatibilities;
    for (int mask = 0; mask < 1 << n; mask++) {
      if (__builtin_popcount(mask) != average) continue;
      unordered_set<int> groupSet;
      int maxNum = 0, minNum = n + 1;
      for (int i = 0; i < n; i++) {
        if ((mask & 1 << i) == 0) continue;
        if (groupSet.count(nums[i]) > 0) break;
        groupSet.emplace(nums[i]);
        if (maxNum < nums[i]) maxNum = nums[i];
        if (minNum > nums[i]) minNum = nums[i];
      }
      if (groupSet.size() == average) incompatibilities.emplace(mask, maxNum - minNum);
    }
    dp[0] = 0;
    for (int mask = 0; mask < 1 << n; mask++) {
      if (dp[mask] == INT_MAX) continue;
      unordered_map<int, int> remainMap;
      for (int i = 0; i < n; i++) {
        if ((mask & 1 << i) >= 1) continue;
        remainMap[nums[i]] = i;
      }
      if (remainMap.size() < average) continue;
      int remainMask = 0;
      for (auto const& pair: remainMap) {
        remainMask |= 1 << pair.second;
      }
      for (int sub = remainMask; sub > 0; sub = remainMask & (sub - 1)) {
        if (incompatibilities.count(sub) == 0) continue;
        dp[mask | sub] = min(dp[mask | sub], dp[mask] + incompatibilities[sub]); 
      }
    }
    return dp[(1 << n) - 1] == INT_MAX ? -1 : dp[(1 << n) - 1];
  }
};

#define MIN(a, b) (a < b ? a : b)
typedef struct {
  int key;
  int val;
  UT_hash_handle hh;
} HashItem;
int bitCount(int n) {
  int ans = 0;
  while (n > 0) {
    ans++;
    n &= n - 1;
  }
  return ans;
}
void freeHashItem(HashItem** pEntry) {
  HashItem *cur, *tmp;
  HASH_ITER(hh, *pEntry, cur, tmp) {
    HASH_DEL(*pEntry, cur);
    free(cur);
  }
}
int minimumIncompatibility(int* nums, int numsSize, int k){
  int n = numsSize, average = n / k;
  int* dp = malloc(sizeof(int) * (1 << n));
  HashItem* incompatibilities = NULL;
  for (int mask = 0; mask < 1 << n; mask++) {
    dp[mask] = INT_MAX;
    if (bitCount(mask) != average) continue;
    HashItem* groupSet = NULL;
    int maxNum = 0, minNum = n + 1;
    for (int i = 0; i < n; i++) {
      if ((mask & 1 << i) == 0) continue;
      HashItem* pEntry = NULL;
      HASH_FIND_INT(groupSet, &nums[i], pEntry);
      if (pEntry != NULL) break;
      pEntry = malloc(sizeof(HashItem));
      pEntry->key = nums[i];
      pEntry->val = 0;
      HASH_ADD_INT(groupSet, key, pEntry);
      if (minNum > nums[i]) minNum = nums[i];
      if (maxNum < nums[i]) maxNum = nums[i];
    }
    if (HASH_COUNT(groupSet) == average) {
      HashItem* pEntry = malloc(sizeof(HashItem));
      pEntry->key = mask;
      pEntry->val = maxNum - minNum;
      HASH_ADD_INT(incompatibilities, key, pEntry);
    }
    freeHashItem(&groupSet);
  }
  dp[0] = 0;
  for (int mask = 0; mask < 1 << n; mask++) {
    if (dp[mask] == INT_MAX) continue;
    HashItem* remainMap = NULL;
    for (int i = 0; i < n; i++) {
      if ((mask & 1 << i) >= 1) continue;
      HashItem* pEntry = NULL;
      HASH_FIND_INT(remainMap, &nums[i], pEntry);
      if (pEntry != NULL) continue;
      pEntry = malloc(sizeof(HashItem));
      pEntry->key = nums[i];
      pEntry->val = i;
      HASH_ADD_INT(remainMap, key, pEntry);
    }
    if (HASH_COUNT(remainMap) < average) continue;
    int remainMask = 0;
    HashItem *cur, *tmp;
    HASH_ITER(hh, remainMap, cur, tmp) {
      remainMask |= 1 << cur->val;
    }
    freeHashItem(&remainMap);
    for (int sub = remainMask; sub > 0; sub = remainMask & (sub - 1)) {
      HashItem* pEntry = NULL;
      HASH_FIND_INT(incompatibilities, &sub, pEntry);
      if (pEntry == NULL) continue;
      dp[mask | sub] = MIN(dp[mask | sub], dp[mask] + pEntry->val);
    }
  }
  freeHashItem(&incompatibilities);
  return dp[(1 << n) - 1] == INT_MAX ? -1 : dp[(1 << n) - 1];
}

# python 3
class Solution:
  def minimumIncompatibility(self, nums: List[int], k: int) -> int:
    n = len(nums)
    dp, average = [sys.maxsize] * (1 << n), n / k
    incompatibilities = dict()
    for mask in range(0, 1 << n):
      if mask.bit_count() != average: continue
      minNum, maxNum, groupSet = n + 1, 0, set()
      for i in range(0, n):
        if (mask & 1 << i) == 0: continue
        if nums[i] in groupSet: break
        groupSet.add(nums[i])
        if minNum > nums[i]: minNum = nums[i]
        if maxNum < nums[i]: maxNum = nums[i]
      if len(groupSet) == average: incompatibilities[mask] = maxNum - minNum
    dp[0] = 0
    for mask in range(0, 1 << n):
      if dp[mask] == sys.maxsize: continue
      remainMap = dict()
      for i in range(0, n):
        if (mask & 1 << i) >= 1: continue
        remainMap[nums[i]] = i
      if len(remainMap) < average: continue
      remainMask = 0
      for _, i in remainMap.items(): remainMask |= 1 << i
      sub = remainMask
      while sub > 0:
        if sub in incompatibilities: dp[mask | sub] = min(dp[mask | sub], dp[mask] + incompatibilities[sub])
        sub = remainMask & (sub - 1)
    return -1 if dp[-1] == sys.maxsize else dp[-1]

class Solution(object):
  def bitCount(self, n):
    ans = 0
    while n > 0:
      ans += 1
      n &= n - 1
    return ans
  def minimumIncompatibility(self, nums, k):
    n = len(nums)
    dp, average = [sys.maxsize] * (1 << n), n / k
    incompatibilities = dict()
    for mask in range(0, 1 << n):
      if self.bitCount(mask) != average: continue
      minNum, maxNum, groupSet = n + 1, 0, set()
      for i in range(0, n):
        if (mask & 1 << i) == 0: continue
        if nums[i] in groupSet: break
        groupSet.add(nums[i])
        if minNum > nums[i]: minNum = nums[i]
        if maxNum < nums[i]: maxNum = nums[i]
      if len(groupSet) == average: incompatibilities[mask] = maxNum - minNum
    dp[0] = 0
    for mask in range(0, 1 << n):
      if dp[mask] == sys.maxsize: continue
      remainMap = dict()
      for i in range(0, n):
        if (mask & 1 << i) >= 1: continue
        remainMap[nums[i]] = i
      if len(remainMap) < average: continue
      remainMask = 0
      for _, i in remainMap.items(): remainMask |= 1 << i
      sub = remainMask
      while sub > 0:
        if sub in incompatibilities: dp[mask | sub] = min(dp[mask | sub], dp[mask] + incompatibilities[sub])
        sub = remainMask & (sub - 1)
    return -1 if dp[-1] == sys.maxsize else dp[-1]