Minimum Incompatibility LeetCode solution in C++

1
const int INF = 1e9;
2

3
class Solution {
4
 public:
5
  int minimumIncompatibility(vector<int> &nums, int k) {
6
    int i, n = nums.size(), subset_size = n / k;
7
    sort(nums.begin(), nums.end());
8

9
    // Pre-calculate the range (max - min) for each subset of nums
10
    // Note that there are (1 << n) subsets (i.e. 2 ^ n subsets) of an array of
11
    // size n
12
    vector<int> range(1 << n, INF);
13

14
    // Each mask represents every possible subset of elements in num (so, "mask"
15
    // == "subset") Specifically, if the bit at position i of mask is set to 1,
16
    // then we include that number in the subset
17
    for (int mask = 1; mask < (1 << n); mask++) {
18
      int small = -1, big = -1;
19
      bool dup = false;
20

21
      // Identify elements that belong to this subset, find the largest &
22
      // smallest, check for duplicates Recall that this array was sorted in the
23
      // beginning of the function
24
      for (i = 0; i < n && !dup; i++)
25
        if (mask & (1 << i)) {
26
          if (small == -1) small = nums[i];
27
          if (big == nums[i]) dup = true;
28
          big = nums[i];
29
        }
30

31
      // If no duplicates were found, then calculate and store the range for
32
      // this subset
33
      if (!dup) range[mask] = big - small;
34
    }
35

36
    vector<int> dp(1 << n, INF);
37
    dp[0] = 0;
38

39
    // Iterate over every mask (i.e. subset) and calculate its minimum sum
40
    for (int mask = 1; mask < (1 << n); mask++) {
41
      // Iterate over every submask for current mask
42
      for (int submask = mask; submask; submask = (submask - 1) & mask) {
43
        // Check that submask has the right number of elements
44
        if (__builtin_popcount(submask) == subset_size)
45
          // Note that mask = submask + (mask ^ submask)
46
          // ==> i.e., mask ^ submask = mask - submask
47
          // In other words, (mask ^ submask) represents those elements in mask
48
          // that are not in submask
49
          dp[mask] = min(dp[mask], range[submask] + dp[mask ^ submask]);
50
      }
51
    }
52
    // dp.back() == dp[(1 << n) - 1];
53
    return dp.back() >= INF ? -1 : dp.back();
54
  }
55
};