1681. Minimum Incompatibility

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        @cache
        def dfs(mask):
            if mask == (1 << n) - 1:
                return 0
            d = {v: i for i, v in enumerate(nums) if (mask >> i & 1) == 0}
            res = inf
            if len(d) < m:
                return res
            for vs in combinations(d.keys(), m):
                nxt = mask
                for v in vs:
                    nxt |= 1 << d[v]
                res = min(res, max(vs) - min(vs) + dfs(nxt))
            return res

        n = len(nums)
        m = n // k
        res = dfs(0)
        dfs.cache_clear()
        return res if res < inf else -1