TC: 90% Pruning Brute Force DFS Explained Python
\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\t\t#this problem is very similar to Fair distribution of cookies but harder because le
```\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\t\t#this problem is very similar to Fair distribution of cookies but harder because len(nums)=16\n        n = len(nums)\n        bagSize = n//k\n        nums.sort()#sorting really helps with pruning conditions\n        def distribute(index, cand): \n            nonlocal ans\n            # Pruning condition 1\n            # n - index - sum(not x for x in bags) represents number of unused items after empty bags have one item,\n            # each unused item will increase the incompatibility (diff) by atleast one\n            # so if the min_increase in compatibility is worse than our current answer, terminate that branch\n            if cand + n - index - sum(not x for x in bags) > ans: return \n            if index == len(nums): ans = cand\n            else: \n                for b_i in range(k):\n                    # bags[b_i][-1] != nums[index] is used to avoid duplicate num in the same bag (not allowed)\n                    # Pruning Condition 2 -> very important\n                    # bags[b_i-1] != bags[b_i] is used to avoid duplicate bags, i.e same bag but different index\n                    if len(bags[b_i])<bagSize and (not bags[b_i] or bags[b_i][-1]!=nums[index]) and (not b_i or bags[b_i-1]!=bags[b_i]):\n                        bags[b_i].append(nums[index])\n                        if len(bags[b_i]) == 1: distribute(index+1, cand)\n                        #two ways to calculate incompatibility\n                        #[0,2,5] => (2-0) + (5-2) == (5-0) = incompatibility\n                        else: distribute(index+1, cand + bags[b_i][-1] - bags[b_i][-2])\n                        bags[b_i].pop()\n        \n        ans = inf\n        bags = [[] for _ in range(k)]\n        distribute(0, 0)\n        return ans if ans < inf else -1\n```
['Depth-First Search', 'Sorting', 'Python']