[Python] Classic Top Down Bitmask DP
There are a number of good bitmask DP explanations on Leetcode, but here, we just make some small adjustments. \nTime: O(n*2^n)\nSpace: O(n)\n\n\nfrom itertools
There are a number of good bitmask DP explanations on Leetcode, but here, we just make some small adjustments. \nTime: O(n*2^n)\nSpace: O(n)\n\n```\nfrom itertools import combinations \nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        groupSize = len(nums) // k\n        @lru_cache(None)\n        def helper(bitmask): # return minimal sum of incompatibilities achievable with unselected indices.\n            if bitmask == 0:\n                return 0\n            else:\n                optimal = float(\'inf\')\n                remaining = [i for i in range(len(nums)) if bitmask & (1 << i)]\n                comb = combinations(remaining,groupSize) \n                for combo in list(comb): \n                    comboElems = [nums[-elem-1] for elem in combo]\n                    if len(set(comboElems)) != groupSize:\n                        continue\n                    else:\n                        newBitmask = bitmask\n                        for idx in combo:\n                            newBitmask ^= 1 << idx\n                        incompat = max(comboElems)-min(comboElems)\n                        optimal = min(optimal,incompat+helper(newBitmask))\n                    \n                return optimal\n            \n        result = helper(2**len(nums)-1)\n        if result == float(\'inf\'):\n            return -1\n        else:\n            return result\n```
[]