python3 dfs backtrack with pruning
Easy to think of backtrack, but pruning is crucial to avoid TLE. Two pruning steps are adopted: first cut all branches with incompatibility larger than already 
Easy to think of backtrack, but pruning is crucial to avoid TLE. Two pruning steps are adopted: first cut all branches with incompatibility larger than already known minimum; second we consider only empty buckets two remove the symmetry between buckets.\n\n# Code\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        self.buckets = [[] for i in range(k)]\n        self.res = float(\'inf\')\n        self.n = len(nums)\n        self.target = self.n // k\n        nums.sort()\n        counter = Counter(nums)\n        m = max(counter.values())\n        self.cur_res = 0\n        if m > k:return -1\n        def dfs(i):\n            if self.cur_res > self.res:#pruning, remove all redundant branches with too large sums\n                return \n            if i  == self.n:\n                self.res = min(self.res,self.cur_res)\n                return\n            for j in range(k):\n                if len(self.buckets[j])<self.target and nums[i] not in self.buckets[j]:\n                    self.buckets[j].append(nums[i])\n                    if len(self.buckets[j])>1:self.cur_res += self.buckets[j][-1] - self.buckets[j][-2] \n                    dfs(i+1)\n                    if len(self.buckets[j])>1:self.cur_res -= self.buckets[j][-1] - self.buckets[j][-2]\n                    self.buckets[j].pop()\n                if self.buckets[j] == []:// pruning 2: all empty buckets are the same, so this would remove all branches with the same combination\n                    break\n        dfs(0)\n        return self.res if self.res<float(\'inf\') else -1\n\n\n\n```
['Python3']