[Python] Simple backtrack with pruning
The idea behind my solution is to put numbers in all possible non empty sets,\nif there are empty sets, put current number in only one empty set.\nPrune backtra
The idea behind my solution is to put numbers in all possible non empty sets,\nif there are empty sets, put current number in only one empty set.\nPrune backtracking if there is already better solution.\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        l = n // k\n        \n        subs = [set() for _ in range(k)]\n        \n        best = float(\'inf\')\n        \n        def backtrack(i):\n            nonlocal best\n            \n\t\t\t# current incompatibility\n            incopat = sum(max(s) - min(s) for s in subs if s)\n            \n            if i == n:\n                best = min(best, incopat)\n                return\n            \n            if best < incopat: #  no need to investigate already bad solution\n                return\n            \n            for j in range(k):\n\t\t\t\t#  try to put current number into:\n\t\t\t\t#  - all valid non empty sets\n\t\t\t\t#  - and the only single empty set\n                if len(subs[j]) == 0:\n                    subs[j].add(nums[i])\n                    backtrack(i + 1)\n                    subs[j].remove(nums[i])\n                    break\n                if nums[i] not in subs[j] and len(subs[j]) < l:\n                    subs[j].add(nums[i])\n                    backtrack(i + 1)\n                    subs[j].remove(nums[i])\n                    \n        backtrack(0)\n        return best if best != float(\'inf\') else -1\n```\n                \n                \n                \n        \n            \n                \n            \n        \n        \n
[]