Minimum Incompatibility LeetCode solution in Java

1
class Solution {
2
  public int minimumIncompatibility(int[] nums, int k) {
3
    Arrays.sort(nums);
4
    k = nums.length / k;
5
    int n = nums.length, INF = 100;
6
    int[][] dp = new int[1 << n][n];
7
    for (int[] d : dp) {
8
      Arrays.fill(d, INF);
9
    }
10
    for (int i = 0; i < n; i++) {
11
      dp[1 << i][i] = 0;
12
    }
13
    for (int i = 1; i < 1 << n; i++) {
14
      int c = Integer.bitCount(i);
15
      for (int j = 0; j < n && c % k == 0; j++) {
16
        for (int w = 0; w < n && (i & 1 << j) > 0; w++) {
17
          if ((i & 1 << w) == 0) {
18
            dp[i | 1 << w][w] = Math.min(dp[i | 1 << w][w], dp[i][j]);
19
          }
20
        }
21
      }
22
      for (int j = 0; j < n && c % k != 0; j++) {
23
        for (int w = j + 1; w < n && (i & 1 << j) > 0; w++) {
24
          if ((i & 1 << w) == 0 && nums[w] != nums[j]) {
25
            dp[i | 1 << w][w] = Math.min(dp[i | 1 << w][w], dp[i][j] + nums[w] - nums[j]);
26
          }
27
        }
28
      }
29
    }
30
    int ans = Arrays.stream(dp[(1 << n) - 1]).min().getAsInt();
31
    return ans == INF ? -1 : ans;
32
  }
33
}