Backtracking + smart optimizations = crazy performance (31ms for Python)
Intuition\n\nThe base idea is backtracking. All possible combinations of subsets are checked using a recursion.\n\nIdeas used to implement major backtracking op
# Intuition\n\nThe base idea is backtracking. All possible combinations of subsets are checked using a recursion.\n\nIdeas used to implement major backtracking optimizations:\n\n1. Backtrack greedily: try combinations with close (to each other) numbers first.\n2. Exit the current backtracking branch as soon as it\'s clear that the minimum score won\'t be beaten. The greedier the combinataion, the higher the chance for it to be the best, therefore the best combination is found quickly, and the rest combinations are skipped early.\n3. Avoid walking same combinations:\n    - Don\'t walk same subsets in different order.\n    - Don\'t walk elements of a subset in different order.\n\n# Approach\n\nThe description implies that you are familiar with the concept of backtracking. The combinations are build subset by subset, each subset is built number by number on is a separate recursion step.\n\nA dictionary is used to store the count of each number in `nums`. It\'s implemented with an array because the variety of numbers is very small and it\'s much faster than a hash-map.\n\nThe backtracking uses it to detect which numbers are not "put" into the subsets yet. The actual subsets aren\'t built, it is not necessary. The dictionary is changed temporarily during the backtracking.\n\nThe current minimum sum of incompatibilities (`minScore`) is also stored globally so that any backtracking branch knows the minimum sum and can exit.\n\nThe state of backtracking is defined by 3 more values:\n\n- `involvedNumsCount` \u2014 the count of numbers from `nums` that has already been "put" into the subsets. When it\'s equal `len(nums)`, the process is complete (all the numbers have been "put" into the subsets).\n- `score` \u2014 the current sum of incompatibilities. It\'s calculated even if the current subset is incomplete. It\'s possible due to this property:\n    ```\n    score\n    = subset[m-1] - subset[0]\n    = (subset[m-1] - subset[m-2])\n      + ...\n      + (subset[2] - subset[1])\n      + (subset[1] - subset[0])\n    ```\n    where `m` is the size of a complete subset.\n- `lastNum` \u2014 if the current subset is incomplete, stores the last number of the subset, otherwise stores `None`. Required to calculate the score for the next step using the formula above, and to know the largest number in the subset.\n\nThe code of the recursion step continues the current combination of subsets. It checks each not yet involved number greedily: from the smallest to the largest. Since the variety of numbers is very limited, a simple loop from `1` to `n` is used.\n\n- If this is a start of a new subset (`lastNum` is `None`), only the first available number is cheched. It\'s excessive to check the other numbers because the first available number is a part of some subset anyway. Checking other numbers would lead to building the same combination of subsets in different order (the order of subsets doesn\'t affect the score).\n- If this is a continuation of an incomplete subset, check only available numbers that are greater than any number inside the current subset. It ensures that permutations of a subset aren\'t checked (the order inside the subsets doesn\'t affect the score).\n\nBefore going into the next recursion step, the algorithm checks whether it\'s impossible to beat the best score in the current situation. If yes, the backtracking branch exits. It\'s checked by comparing the most optimistic final score with the current minimum final score (`minScore`). The optimistic score is calculated assuming that the rest subsets will contain only adjecent numbers.\n\n# Complexity\n- Time complexity:\n\nI don\'t know, sorry.\n\nIf there was no fast exit, the number of steps would be the number of ways to split `nums` into `k` equal subsets: `O(n! / ((n/k)!)^k / k!)` (in the worst case).\n\n- Space complexity:\n\nThe `nums` counter and the depth of the recursion. Both are `O(n)` in the worst case.\n\n# Code\n```python\nclass Solution:\n  def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n    n = len(nums)\n    subsetSize = int(n / k)\n    numCounts = [0] * (n + 1)\n    for num in nums:\n      numCounts[num] += 1\n    minScore = math.inf\n\n    def backtrack(involvedNumsCount, currentScore, lastNum):\n      nonlocal minScore\n\n      if involvedNumsCount == n:\n        minScore = currentScore\n        return\n\n      involvedNumsCount += 1\n      subsetEnd = involvedNumsCount % subsetSize == 0\n\n      if lastNum is None:\n        for num in range(1, n + 2 - subsetSize):\n          if numCounts[num] == 0:\n            continue\n\n          numCounts[num] -= 1\n          backtrack(involvedNumsCount, currentScore, None if subsetEnd else num)\n          numCounts[num] += 1\n\n          # Avoids checking same subsets in different order\n          break\n      else:\n        numsLeft = n - involvedNumsCount\n        # Assuming that the other numbers are adjacent\n        optimisticRestScore = numsLeft - floor(numsLeft / subsetSize)\n        \n        # `lastNum + 1` as the start avoids checking permutations of subsets\n        for num in range(lastNum + 1, n + 1):\n          if numCounts[num] == 0:\n            continue\n\n          nextScore = currentScore + num - lastNum\n          if nextScore + optimisticRestScore >= minScore:\n            # The next nums will give even bigger score\n            return\n\n          numCounts[num] -= 1\n          backtrack(involvedNumsCount, nextScore, None if subsetEnd else num)\n          numCounts[num] += 1\n    \n    backtrack(0, 0, None)\n    return minScore if minScore is not math.inf else -1\n```
['Backtracking', 'Greedy', 'Python3']