[Python3] backtracking
Algo\nThis is an organized brute force approach. We simply put the elements following the rule into stacks and compute incompatibility. Here, the two tricks are
**Algo**\nThis is an organized brute force approach. We simply put the elements following the rule into stacks and compute incompatibility. Here, the two tricks are \n1) `if cand + len(nums) - i > ans: return` meaning that if there is no chance for the current run to get smaller incompability we simply return;\n2) `len(stack[ii]) < len(nums)//k and (not stack[ii] or stack[ii][-1] != nums[i]) and (not ii or stack[ii-1] != stack[ii])` meaning current stack has enough space for an extra element, `nums[i]` hasn\'t been added to this stack yet, and it is different from the previous stack (otherwise what\'s the point of adding it to an identical stack). \n\nWithout these two tricks, one would have TLE. \n\n**Implementation**\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        \n        def fn(i, cand): \n            """Populate stack and compute minimum incompatibility."""\n            nonlocal ans \n            if cand + len(nums) - i - sum(not x for x in stack) > ans: return \n            if i == len(nums): ans = cand\n            else: \n                for ii in range(k): \n                    if len(stack[ii]) < len(nums)//k and (not stack[ii] or stack[ii][-1] != nums[i]) and (not ii or stack[ii-1] != stack[ii]): \n                        stack[ii].append(nums[i])\n                        if len(stack[ii]) == 1: fn(i+1, cand)\n                        else: fn(i+1, cand + stack[ii][-1] - stack[ii][-2])\n                        stack[ii].pop()\n        \n        ans = inf\n        stack = [[] for _ in range(k)]\n        fn(0, 0)\n        return ans if ans < inf else -1\n```\n\nFor those who are uncomfortable with `nonlocal` variables, an alternative implementation is given below \n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        \n        def fn(i, cand=0, ans=inf):\n            """Return minimum incompatibility via backtracking."""\n            if cand + len(nums) - i - sum(not x for x in stack) >= ans: return ans # early return \n            if i == len(nums): return cand\n            for ii in range(k): \n                if len(stack[ii]) < len(nums)//k and (not stack[ii] or stack[ii][-1] != nums[i]) and (not ii or stack[ii-1] != stack[ii]): \n                    stack[ii].append(nums[i])\n                    if len(stack[ii]) == 1: ans = fn(i+1, cand, ans)\n                    else: ans = fn(i+1, cand + stack[ii][-1] - stack[ii][-2], ans)\n                    stack[ii].pop()\n            return ans \n        \n        stack = [[] for _ in range(k)]\n        ans = fn(0)\n        return ans if ans < inf else -1\n```
['Python3']