Python DFS Backtracking Pruning Solution, faster than 100%(91ms)
\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        ctrNums = Counter(nums)\n        if any(ctrNums[num] > k for n
```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        ctrNums = Counter(nums)\n        if any(ctrNums[num] > k for num in ctrNums):\n            return -1\n        bags, res, sz = [[] for _ in range(k)], inf, len(nums)\n        maxNumsperBag, numbers = sz // k, sorted(ctrNums.keys())\n        nums.sort()\n        curSize, curBag, gaps, gapsSum = 0, [], defaultdict(int), defaultdict(int)\n        cntUniqueNums = len(numbers)\n        for i in range(1, cntUniqueNums):\n            gaps[numbers[i]] = numbers[i] - numbers[i - 1]\n        for i in range(sz - 1, -1, -1):\n            curBag.append(gaps[nums[i]])\n            curBag.sort()\n            curSize += gaps[nums[i]]\n            gapsSum[i, 0] = curSize\n            for empty in range(1, min(k + 1, len(curBag))):\n                gapsSum[i, empty] = gapsSum[i, empty - 1] - curBag[-empty]\n        \n        def dfs(i: int, curRes: int, emptyBags: int) -> None:\n            nonlocal res\n            if i == sz:\n                res = min(res, curRes)\n                return\n            if curRes + gapsSum[i, emptyBags] >= res: \n                return\n            for j in range(k):\n                if (j > 0 and bags[j] == bags[j - 1]) or (bags[j] and bags[j][-1] == nums[i]) or (len(bags[j])) == maxNumsperBag:\n                    continue\n                else:\n                    bags[j].append(nums[i])\n                    if len(bags[j]) == 1:\n                        dfs(i + 1, curRes, emptyBags - 1)\n                    else:\n                        dfs(i + 1, curRes + bags[j][-1] - bags[j][-2], emptyBags)\n                    bags[j].pop()\n        \n        dfs(0, 0, k)\n        return res\n```
['Dynamic Programming', 'Backtracking', 'Python']