1. // 优化四：指令集优化，让CPU使用POPCNT指令，从而加速__builtin_popcount
  2. #pragma GCC target ("sse4.2")
  3. __builtin_popcount(state) == sz;   该指令计算state中二进制1的个数

5619. 最小不兼容性

给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。 一个子集的 不兼容性 是该子集里面最大值和最小值的差。 请你返回将数组分成 k 个子集后，各子集 不兼容性 的 和 的 最小值 ，如果无法分成分成 k 个子集，返回 -1 。 子集的定义是数组中一些数字的集合，对数字顺序没有要求。

  • 1 <= k <= nums.length <= 16
  • nums.length 能被 k 整除。
  • 1 <= nums[i] <= nums.length

思路

  • N有限定范围，即记忆化回溯 状态压缩 分治 - 图1，显然可以使用状态压缩来表示数组所有的子集（状态）,总状态数为记忆化回溯 状态压缩 分治 - 图2.递归求解每个状态数所对应的最小不兼容性，最后可得总集即状态数为记忆化回溯 状态压缩 分治 - 图3状态数的最小不兼容性。

在枚举分组方案时，若朴素的递归记忆化回溯 状态压缩 分治 - 图4,总复杂度

  • 采用分治，即记忆化回溯 状态压缩 分治 - 图5,尝试所有可能将数组分成两堆的方案，并对左堆和右堆递归进行求解，为了避免重复计算，需要使用记忆化。
    • 如何将数组尝试所有可能分成两堆？

对于某个状态state的所有位来说，仅有当前位为1的情况下需要考虑。

  1.   - `state & (state - 1)`：`state`从左到右第一个1为界，将其分为两堆。有
  2.      - `leftState=state & (state-1)`
  3.      - `rightState=leftState^state`
  4.   - `(leftState - 1) & state`:`state`从左往右第二个1位界，将其分为两堆。`rightState`求法如上。
  • 递归终止条件

当前状态state中1的个数与规定子集长度相同时，判断该子集是否符合条件，若不符合，则设置其不兼容性为INF，否则求得其不兼容性。
对于优化条件，可使用5种优化来优化上述递归程序。

  1. 判断是否存在不兼容性
    1. 子集长度=1
    2. 数组中有元素数量>k
  2. 记忆化

记录每个状态的最小不兼容性。

  1. 子集枚举优化
    1. 若state中1的个数不能整数k，则该子集不具备不兼容性，continue
    2. 若求得leftState的不兼容性已＞当前总和的最优值，显然该状态已不具备最优，continue
  2. 排序

不兼容性=集合中最大值和最小值只差，故将整个数组排序，所有子集均为排序数组，则每个子集的不兼容性即为首尾相减的值

算法

设N=nums.size(),sz=k/N; 记忆化列表为memo[]=-1

  • recur(state):
    • 当前状态是否在记忆化列表中,memo[state]!=-1
    • 当前子集长度是否等于sz。
      • 得到对应的子集，并判断子集中是否有重复元素
      • 若无，则更新memo[state]=subset[sz-1]-subset[0]
    • 遍历所有分成两堆的状态，并求解左右两堆
  • 主函数：
    • 判断是否满足求解不兼容性的条件
    • 初始化memo[]=-1 ```cpp // 优化四：指令集优化，让CPU使用POPCNT指令，从而加速__builtin_popcount

      pragma GCC target (“sse4.2”)

const int INF = 0x3f3f3f3f; int memo[65536], v[16];

class Solution { int n, k, sz; vector nums; int solve(int state) { if (memo[state] != -1) return memo[state];

  1.     // 边界条件：当前集合刚好包含n/k个元素，不需要继续划分
  2.     if (__builtin_popcount(state) == sz) {
  3.         //__builtin_popcount：计算二进制1个数
  4.         for (int i = 0,idx=0; i < n; ++i)
  5.             if (state & (1 << i))//subset数组元素索引，用v来存储
  6.                v[idx++] = i;
  7.         //判断v中是否存在相同元素，若存在则为INF；
  8.         for (int i = 0; i + 1 < sz; ++i)
  9.             if (nums[v[i]] == nums[v[i + 1]])
  10.                 return memo[state] = INF;
  11.         //否则则为首尾相减
  12.         return memo[state] = nums[v[sz - 1]] - nums[v[0]];
  13.     }
  15.     int ans = INF;
  16.     //如下为重点！！！
  17.     // 优化二：子集枚举优化
  18.     for (int sub = state & (state - 1); sub; sub = (sub - 1) & state) {
  19.         if (__builtin_popcount(sub) % sz != 0)
  20.             continue;
  21.         int left = solve(sub);
  23.         // 优化三：如果左边的最优值已经达到了当前总和的最优值，则不需要继续计算右边。
  24.         if (left >= ans)
  25.             continue;
  26.         int right = solve(state ^ sub);
  27.         ans = min(ans, left + right);
  28.     }
  29.     return memo[state] = ans;
  30. }

public: int minimumIncompatibility(vector& nums, int k) { n = nums.size(); this->k = k; sz = n / k; //子集大小

  1.     // 优化一：每个子集的大小为1，不兼容性显然为0，总和也是0。
  2.     // 这种情况的筛除非常重要，因为它需要最多的枚举次数。
  3.     if (sz == 1)
  4.         return 0;
  6.     sort(nums.begin(), nums.end());
  7.     //判断不兼容性是否存在
  8.     vector<int> cnt(n + 1);
  9.     for (int num : nums) {
  10.         cnt[num]++;
  11.         if (cnt[num] > k)
  12.             return -1;
  13.     }
  15.     this->nums = nums;
  16.     for (int i = 0; i < (1 << n); ++i)
  17.         memo[i] = -1;
  18.     return solve((1 << n) - 1);
  19. }

};

```

复杂度分析

  • 时间复杂度：遍历所有的状态，即[1,….,stateMax],此复杂度为记忆化回溯 状态压缩 分治 - 图6,在每个状态递归（对每个状态分组）中，最糟糕的情况下,复杂度为记忆化回溯 状态压缩 分治 - 图7,故整体复杂度为记忆化回溯 状态压缩 分治 - 图8
  • 空间复杂度：存储16位的所有状态需要记忆化回溯 状态压缩 分治 - 图9