Bitmasking DP easy to understand
Intuition\n1. We have around 16 items, so we are able to construct a DP with 2^16\n2. Inside the DP, we need to pick n//k items to form a groupd, it will take C
# Intuition\n1. We have around 16 items, so we are able to construct a DP with 2^16\n2. Inside the DP, we need to pick n//k items to form a groupd, it will take C(Size, n//k) at maximum, then the time complexity will be reduced gradually because we reduced our search space to n//k items everytime.\nC(Size, n//k) + C(Size - n//k, n//k) ... + C(Size - k*n//k, n//k) inside the DP.\n3. Overall the time complexity should be 2^16*C(Size, k) which is pretty small to pass all test cases.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3\n\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        size = n //k\n        @lru_cache(None)\n        def dp(mask):\n            if mask == 2**n - 1:\n                return 0\n\n            candidates = []\n            dupplicated = set()\n            for i in range(n):\n                if mask >> i & 1 == 1 or nums[i] in dupplicated:\n                    continue\n\n                candidates.append(i)\n                dupplicated.add(nums[i])\n\n            ans = inf\n            for indexes in combinations(candidates, size):\n                minSofar = inf\n                maxSofar = -inf\n                newMask = 0\n                for i in indexes:\n                    minSofar = min(nums[i], minSofar)\n                    maxSofar = max(nums[i], maxSofar)\n                    newMask = newMask | (1 << i)\n\n                ans = min(ans, maxSofar - minSofar  + dp(mask | newMask))\n            \n            return ans\n\n        ans = dp(0)\n        return -1 if ans == inf else ans\n\n            \n\n```
['Dynamic Programming', 'Bitmask', 'Python3']