backtracking and prune
I didn\'t get it in the contest but I learned this trick after contest. It costs 4000ms so I think there must be some other solutions which are better, or maybe
I didn\'t get it in the contest but I learned this trick after contest. It costs 4000ms so I think there must be some other solutions which are better, or maybe there are other prune situations I don\'t know.\n```\n\n# load local leetcode lib\nimport pathlib\nlc_lib_path = pathlib.Path(\'../lc_lib.py\')\nif lc_lib_path.exists():\n    import sys\n    sys.path.insert(0, \'..\')\n    from lc_lib import *\n\nold_print = print\ndef print(*args, **kwargs):\n    if lc_lib_path.exists():\n        old_print(*args, **kwargs)\n\nfrom sortedcontainers import SortedList\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        print(nums)\n        n = len(nums)\n        elements_per_group = n//k\n        groups = [SortedList() for _ in range(k)]\n        inf = float(\'inf\')\n        result = inf\n\n        def dfs(i, cur_res):\n            nonlocal result\n            if i==n:\n                result = min(result, cur_res)\n\n            if cur_res>=result:\n                return\n\n            num = nums[i]\n            for j in range(k):\n                group = groups[j]\n                if any([\n                    len(group)>=elements_per_group,\n                    j>0 and group==groups[j-1],\n                    num in group,\n                   ]):\n                    continue\n                res_add = 0\n                if group and (num<group[0] or num>group[-1]):\n                    res_add = min(abs(num-group[0]), abs(num-group[-1]))\n                group.add(num)\n                dfs(i+1, cur_res+res_add)\n                group.remove(num)\n                    \n        dfs(0, 0)\n        return result if result!=inf else -1\n\nif __name__==\'__main__\':\n    if lc_lib_path.exists():\n        s = Solution()\n\n        nums = [1,2,1,4]\n        k = 2\n        r = s.minimumIncompatibility(nums,k)\n        print(r)\n        print(\'-\'*30)\n\n        nums = [7,3,16,15,1,13,1,2,14,5,3,10,6,2,7,15]\n        k = 8\n        r = s.minimumIncompatibility(nums,k)\n        print(r)\n        print(\'-\'*30)\n\n\n```
[]