[Python] brute force with some pre-pruning
Key to not TLE on this problem is, given the set of numbers nums, only consider subset of nums that is of size n//k, and with only unique values. So we\'ll firs
Key to not TLE on this problem is, given the set of numbers `nums`, only consider subset of `nums` that is of size n//k, and with only unique values. So we\'ll first generate only valid candidate subsets, and for convinience and efficiency, each candidate subset will be represented a tuple: `(bitmask, diff)`. The `bitmask` will have `n//k` bits set where if bit-i is set, it means `nums[i]` is part of the candidate subset. `diff` is the max{values in subset} - min {values in subset}. Then we\'ll go through all possible k combinations of the candidate subsets and see which results in the minimum incompatibility value.\n\nThe key recurrence is:\nLet `s` represent the set of numbers selected in k partitions and `p` a subset of `s` containing `n//k` unique values. f(s) be the minimum discrepancy over them, then:\n`f(s) = argmin[all valid p \u2286 s]{f(s - p) + max{all values in p} - min{all values in p}}`\n\nHere\'s the top-down recursive version which is easier to come up first than the dynamic programming version:\n```\n    def minimumIncompatibility_recursive_topdown(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        ALL_SELECTED = (1 << n) - 1\n        valid_subsets = self.gen_valid_subsets(nums, k)\n            \n        @functools.lru_cache(None)\n        def f(s):\n            if s == ALL_SELECTED:\n                return 0\n            \n            min_incomp = float(\'inf\')\n            for i in range(len(valid_subsets)):\n                if s & valid_subsets[i][0] != 0:\n                    # If we do choose to use the i-th subset of numbers, none of them should\n                    # have been previously selected by a different subset\n                    continue\n\n                min_incomp = min(min_incomp, f(s | valid_subsets[i][0]) + valid_subsets[i][1])\n            \n            return min_incomp\n                \n        result = f(0)\n        return result if result != float(\'inf\') else -1\n```\n\nThen mechanically convert the above to use dynamic programming:\n```\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        n = len(nums)       \n\t\tALL_SELECTED = (1 << n) - 1\n        valid_subsets = self.gen_valid_subsets(nums, k)\n\n        f = [float(\'inf\')] * (1 << n)\n        f[0] = 0\n        for s in range(1, 1 << n):\n            if bin(s).count("1") % (n//k) != 0:\n                continue\n            for i in range(len(valid_subsets)):\n                if s & valid_subsets[i][0] != valid_subsets[i][0]:\n                    continue\n                f[s] = min(f[s], f[s ^ valid_subsets[i][0]] + valid_subsets[i][1])\n        \n        return f[ALL_SELECTED] if f[ALL_SELECTED] != float(\'inf\') else -1\n```\n\nBoth would use the standard recursive function to generate candidate subsets:\n```\n    def gen_valid_subsets(self, nums, k):\n        n = len(nums)\n        set_size = n // k\n        subsets = []\n        def choose(i, seen, s, max_val, min_val):\n            if len(seen) == set_size:\n                # Each valid tuple contains the bitmask representing the subset of n//k numbers\n                # selected and the discrepancy value\n                subsets.append((s, max_val - min_val))\n                return\n\n            if i == n:\n                return\n\n            if nums[i] not in seen:\n                seen.add(nums[i])\n                choose(i + 1, seen, s | (1 << i), max(max_val, nums[i]), min(min_val, nums[i]))\n                seen.remove(nums[i])\n\n            choose(i + 1, seen, s, max_val, min_val)\n\n        choose(0, set(), 0, float(\'-inf\'), float(\'inf\'))\n        return subsets \n```\n
[]