[Python] Top Down DP
\n\nApproach: (click to show)\n\nEach bin must contain ```nums.length / k``` numbers.\nIterate over the ```k``` bins and generate all possible\ncombinations of 
<details>\n\n<summary><b>Approach:</b> (click to show)</summary>\n\nEach bin must contain ```nums.length / k``` numbers.\nIterate over the ```k``` bins and generate all possible\ncombinations of numbers that can go into each bin.\n\nIf a combination contains two of the same number,\nthen skip that combination.\n\nThe cost of selecting a certain combination for a bin\nis the maximum number in the combination minus\nthe minimum number in the combination.\n\nThe total cost is the cost of the combination selected\nplus the minimum cost that can be achieved with the\nremaining numbers.\n\n</details>\n\n<details>\n\n<summary><b>Optimizations:</b> (click to show)</summary>\n\n<br>\n\n1. If ```nums.length == k``` then there is one bin for every number, the answer is zero.\n2. If there are more than ```k``` of any number, then there is no solution, the answer is -1.\n\n</details>\n\n<br>\n\n```python\n# Runtime: 7812 ms (see below for faster solution)\ndef minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\n\t@functools.lru_cache(None)\n\tdef helper(i, nums):\n\t\tif max(collections.Counter(nums).values()) > k - i:\n\t\t\treturn math.inf\n\n\t\tif i == k - 1:\n\t\t\treturn max(nums) - min(nums)\n\n\t\tbest = math.inf\n\t\tcombos = itertools.combinations(list(range(len(nums))), bin_size)\n\t\tfor combo in combos:\n\t\t\tnumbers = [nums[i] for i in combo]\n\t\t\tif len(set(numbers)) == len(numbers):\n\t\t\t\tcombo = set(combo)\n\t\t\t\tbest = min(best, max(numbers) - min(numbers) + helper(i+1, tuple([n for i,n in enumerate(nums) if i not in combo])))\n\t\treturn best\n\n\tif k == len(nums): return 0\n\tbin_size = len(nums) // k\n\tres = helper(0, tuple(nums))\n\treturn -1 if (res == math.inf) else res\n```\n\n<br>\n\n<details>\n\n<summary><b>Annotated Code:</b> (click to show)</summary>\n\n```python\n#Runtime: 7812 ms: (see below for faster implementation)\ndef minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\n\t# If any number occurs more than k times, there is no solution\n\tc = collections.Counter(nums)\n\tif max(c.values()) > k:\n\t\treturn -1\n\n\t# If there is one bin for each number then the answer zero\n\tif k == len(nums):\n\t\treturn 0\n\n\t# This is the size of each bin\n\tbin_size = len(nums) // k\n\n\t@functools.lru_cache(None)\n\tdef helper(i, nums):\n\n\t\t# k - 1 bins have been filled, if all the numbers in nums are distinct the remaining nums get binned together\n\t\tif i == k - 1:\n\t\t\treturn max(nums) - min(nums) if len(set(nums)) == len(nums) else math.inf\n\n\t\tbest = math.inf\n\n\t\t# Consider all combinations of bin_size numbers to place in the current bin\n\t\tcombos = itertools.combinations(list(range(len(nums))), bin_size)\n\t\tfor combo in combos:\n\t\t\tnumbers = [nums[i] for i in combo]\n\n\t\t\t# Do not place two of the same number into a bin\n\t\t\tif len(set(numbers)) == len(numbers):\n\t\t\t\tcombo = set(combo)\n\t\t\t\tbest = min(best, max(numbers) - min(numbers) + helper(i+1, tuple([n for i,n in enumerate(nums) if i not in combo])))\n\n\t\treturn best\n\n\treturn helper(0, tuple(nums))\n```\n\n</details>\n\n<details>\n\n<summary><b>Faster Solution:</b> 3656 ms (click to show)</summary>\n\nThis is the same approach as above, except instead of keeping track\nof a tuple of the remaining numbers. We keep track of the count for each number:\n\n```\nnums = (1, 1, 1, 2, 3, 3, 4, 5)\nbecomes\nnums = ((3, 1), (1, 2), (2, 3), (1, 4), (1, 5))\n```\n\nThis makes the code less readable, but faster to execute.\nThe reason is because in the first solution, we had to make sure that\ntwo of the same number did not get grouped together.\n\nBy grouping numbers like so, it is guaranteed guarantee that two \nof the same number will not get grouped together.\n\n```python\n# Runtime: 3656 ms\ndef minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\n\t@functools.lru_cache(None)\n\tdef helper(i, nums):\n\n\t\tif max(nums)[0] > k - i:\n\t\t\treturn math.inf\n\n\t\tif i == k - 1:\n\t\t\treturn max(nums)[1] - min(nums)[1]\n\n\t\tbest = math.inf\n\t\tcombos = itertools.combinations(list(range(len(nums))), bin_size)\n\t\tfor combo in combos:\n\t\t\tnumbers = [nums[j][1] for j in combo]\n\t\t\tcombo = set(combo)\n\t\t\tnew_nums = []\n\t\t\tfor j in range(len(nums)):\n\t\t\t\tif j in combo:\n\t\t\t\t\tf, n = nums[j]\n\t\t\t\t\tif f > 1:\n\t\t\t\t\t\tnew_nums.append((f-1,n))\n\t\t\t\telse:\n\t\t\t\t\tnew_nums.append(nums[j])\n\t\t\tbest = min(best, max(numbers) - min(numbers) + helper(i+1, tuple(new_nums)))\n\t\treturn best\n\n\tif k == len(nums): return 0\n\tc = collections.Counter(nums)\n\tbin_size = len(nums) // k\n\tnums = tuple([(c[num], num) for num in c])\n\tres = helper(0, nums)\n\treturn -1 if (res == math.inf) else res\n```\n\n</details>
[]