[Python] Easy-Understanding DFS with Memo
Idea:\nLet\'s assume the problem is for dictionary d, we need to divide them into k groups with each group size as count, we can pick a group of numbers first a
**Idea:**\nLet\'s assume the problem is for dictionary `d,` we need to divide them into `k` groups with each group size as `count`, we can pick a group of numbers first and transform the problem to a sub-problem of `(new_d, k - 1, count)`\n**Implementation**\nUse `frozenset` to hash\n```\nimport collections\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        @lru_cache(None)\n        def dfs(d, k, count):\n            d = dict(d)\n            # Special cases\n            if k == 1:\n                if len(d) >= count:\n                    return max(d.keys()) - min(d.keys())\n                else:\n                    return -1\n            if count == 1:\n                return 0\n            if len(d) < count:\n                return -1\n            for key in d:\n                if d[key] > k:\n                    return -1\n            \n            # Pick a group first\n            from itertools import combinations   \n            res = float(\'inf\')\n            perm = combinations(d.keys(), count) \n            for i in list(perm):\n                gap = max(i) - min(i)\n                for cur in i:\n                    d[cur] -= 1\n                    if d[cur] == 0:\n                        del d[cur]\n                        \n                # Update result\n                nex = dfs(frozenset(d.items()), k - 1, count)\n                if nex != -1:\n                    res = min(res, gap + nex)\n                for cur in i:\n                    if cur not in d:\n                        d[cur] = 0\n                    d[cur] += 1\n\n            return res if res != float(\'inf\') else -1\n        \n        d = {}\n        for num in nums:\n            if num not in d:\n                d[num] = 0\n            d[num] += 1\n            \n        return dfs(frozenset(d.items()), k, len(nums) // k)\n```
['Python', 'Python3']