[Python] Bruteforce/DP
Idea: store the results of all valid subsets of the original array, there are at most 2^16=65536 states that we need to calculate.\n\nclass Solution:\n    def m
Idea: store the results of all valid subsets of the original array, there are at most `2^16=65536` states that we need to calculate.\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        d=len(nums)//k # the length of each partition\n        \n        @lru_cache(None)\n        def helper(nums):\n            if not nums:\n                return 0\n            ret=10**15\n            for a in combinations(nums,d): # choose a as a partition\n                if len(set(a))<d: # check for duplicates\n                    continue\n                left=list(nums) # numbers left after removing partition a\n                for v in a:\n                    left.remove(v)\n                ret=min(ret,max(a)-min(a)+helper(tuple(left)))\n            return ret\n        \n        ans=helper(tuple(nums)) # turn the input into a tuple so the function can be cached\n        return ans if ans!=10**15 else -1\n```\n**Edit**: **Optimization** (credit to @Gowe, @bismeet): we can create each partition by `combinations(set(nums),d)` and skip the check for duplicates (see details in the comments).\n\n**Time complexity** (credit to @apluscs): `O(n *(n choose d)*2^n)`, where `d` is the size of each partition. We have `O(2^n)` states, for each state we loop over `O(n choose d)` cases and for each case we need to create a set/tuple of length `O(n)`. \nHowever, this seems to be overestimating the complexity by a lot, as for `n=16` we get the worst case : `16*(16 choose 8)*2^16=1.3e10`. My guess is that on average we only calculate for the subsets whose sizes are multiples of `d` and not all `2^n` states are needed. I tried to calculate the complexity without approximations and got the worst cast is about `2.8e7` when `n=16, d=4`.
[]