Efficient JS solution - Backtracking + Memo (Beat 100% both time and memory)
\n\nPro tip: Xie? of course, Xie \uD83D\uDC9C\n\n# Complexity\n- Let n = nums.length\n- Time complexity: O(n * 2^n)\n- Space complexity: O(2^n)\n\n# Code\njs\nl
![image.png](https://assets.leetcode.com/users/images/dade339a-95e5-40f2-8714-597a7d131412_1706595104.248392.png)\n\nPro tip: Xie? of course, Xie \uD83D\uDC9C\n\n# Complexity\n- Let `n = nums.length`\n- Time complexity: $$O(n * 2^n)$$\n- Space complexity: $$O(2^n)$$\n\n# Code\n```js\nlet memo = new Uint8Array(65536);\nlet selections = new Uint8Array(16);\n\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar minimumIncompatibility = function (nums, k) {\n  let n = nums.length;\n  let s = Math.floor(n / k);\n  nums.sort((a, b) => a - b);\n\n  let l = 0;\n  for (let i = 0; i < n; ++i) {\n    if (nums[i] != nums[i + 1]) {\n      if (i - l + 1 > k) return -1;\n      l = i + 1;\n    }\n  }\n\n  let full = 1 << n;\n  let available = full - 1;\n  memo.fill(0, 0, available + 1);\n  let res = 1000;\n  let cur = 0;\n\n  function bt(d) {\n    if (d % s) {\n      let btRes = 1000;\n\n      for (let b = selections[d - 1] + 1; b < n; ++b) {\n        if (!(available & (1 << b))) continue;\n        if (nums[selections[d - 1]] == nums[b]) continue;\n\n        selections[d] = b;\n        available ^= 1 << b;\n        btRes = Math.min(btRes, bt(d + 1));\n        available ^= 1 << b;\n      }\n\n      return btRes;\n    } else {\n      let lastSum = nums[selections[d - 1]] - nums[selections[d - s]];\n      if (cur + lastSum >= res) return 1000;\n      if (d == n) {\n        res = cur + lastSum;\n        return lastSum;\n      }\n      if (memo[available]) {\n        res = Math.min(res, cur + lastSum + memo[available]);\n        return lastSum + memo[available];\n      }\n\n      for (let b = 0; b < n; ++b) {\n        if (available & (1 << b)) {\n          cur += lastSum;\n          selections[d] = b;\n          available ^= 1 << b;\n          let btRes = bt(d + 1);\n          available ^= 1 << b;\n          memo[available] = btRes;\n          if (d) btRes += lastSum;\n          cur -= lastSum;\n          return btRes;\n        }\n      }\n    }\n  }\n\n  return bt(0);\n};\n```
['Backtracking', 'Bit Manipulation', 'Bitmask', 'JavaScript']