[Python] simple backtracking beats 100%
\npython\nclass Solution(object):\n    def minimumIncompatibility(self, nums, k):\n        nums.sort(reverse = True)\n        upperbound = len(nums) // k\n     
![image](https://assets.leetcode.com/users/images/da932706-954a-4246-821e-95c9c8078733_1607233824.1326246.png)\n```python\nclass Solution(object):\n    def minimumIncompatibility(self, nums, k):\n        nums.sort(reverse = True)\n        upperbound = len(nums) // k\n        arr = [[] for _ in range(k)]\n        self.res = float(\'inf\')\n        def assign(i):\n            if i == len(nums):\n                self.res = min(self.res, sum(arr[i][0]-arr[i][-1] for i in range(k)))\n                return True\n            flag = 0\n            for j in range(k):\n                if not arr[j] or (len(arr[j]) < upperbound and arr[j][-1] != nums[i]):\n                    arr[j].append(nums[i])\n                    if assign(i+1):\n                        flag += 1\n                    arr[j].pop()\n                if flag >= 2: break\n            return flag != 0\n        if max(collections.Counter(nums).values()) > k: return -1\n        assign(0)\n        return self.res\n```\n\nBacktracking is a very time consuming algorithm. If we don\'t have early break, its time complexity will be O(n!) (for example Hamiltonian and NQueens problems). So we usually need to have an early break condition, which is a tricky part.\n\nIn this case, I implemented backtracking with two attemps (nums[i] can be assigned to arr[j] and arr[j+1]). A simple and fast solution.
['Backtracking', 'Python', 'Python3']