Python 3: FT 100.00% 89 ms, LMT 90%: DFS + Backtracking, Exploration and Pruning Optimizations
Intuition\n\nThis problem is really hard. My early attempts all resulted in either wrong answers (greedy) or TLE.\n\nEventually I realized that the partitioning
# Intuition\n\nThis problem is really hard. My early attempts all resulted in either wrong answers (greedy) or TLE.\n\nEventually I realized that the partitioning logic is "complicated," in the sense that the answer in the general cannot be done with any kind of greedy algorithm with basic rules. There are lots of edge cases.\n\nSo the backup is "try all the valid partitionings and see which one is best." Aka DFS + backtracking!\n\nThe basic structure of DFS + backtracking algorithms is that we have a bunch of elements to assign to partitions. We can either\n* go partition by partition, picking elements for partition `i` and moving on to `i+1`\n* or go element-by-element, putting it in each partition and moving on to element `i+1`\n\nPicking a group of `k` elements is harder IMO than going element-by-element, so I chose element-by-element.\n\nSo the idea of the algorithm is this:\n* for each next index `i`\n* if `i` is out of bounds, we assigned all elements. update the answer\n* otherwise, consider placing `nums[i]` in every partition that\n  * is not full\n  * does not already have a copy of `nums[i]`\n* for each possible "target" partition, add `nums[i]` and proceed\n* then backtrack as usual\n\n# Approach\n\nThat approach, done literally, gives TLE.\n\nDFS+backtracking solutions are often VERY slow for problems like this because they run in factorial time (even worse than exponential!) - they explore all partitionings in this case, which can be a VAST quantity.\n\nSo anything we do to accelerate is good.\n\n## Optimization 1: "Greater `j` Only"\n\nFor `n == nums[i]`, suppose we assign value `n` to partition `j`.\n\nThen for `n == nums[i+1]`, do NOT consider placing it at indices `j\' <= j`.\n\n`j\' != j` is because we can\'t have duplicates in any partition.\n\n`j\' < j` is because we want to avoid the following edge case:\n* suppose we have two copies of `n`\n* then maybe we put the first copy at `j=0`, and the second copy of `j=1`. No problem there\n* but then later, we try putting the first in `j=1` and the second in `j=0`\n\nThis is obviously bad because the resulting solution will be the same, but we did twice as much work - **we should avoid exploring effectively duplicate states**.\n\nThis specific situation, where you\'re DFS+backtracking code effectively backtracks itself by repeating states, is common.\n\nThe typical solution, that I implement here, is to **enforce forward progress.** In particular:\n* if an earlier stack frame skipped over indices `0..j-1`\n* then the current stack frame and all later ones should skip those as well\n\nThis same optimization shows up when you need to take `k` elements from an array, and there are some duplicates. If you\'re careful, you\'ll end up doing `2**numDuplicates` work because you\'ll explore all patterns of taking and not taking each number. But in reality, you want to explore just the effect of taking each number of copies.\n\n## Optimization 2: Only Try Effectively Unique Partitions\n\nSuppose we\'re placing element `i`, and we already tried all solutions (or lack thereof) from appending `nums[i]` to a partition with existing values `[1, 3, 10]`.\n\nThen we should never try adding `nums[i]` to another partition with `[1, 3, 10]`. Why? Same reason as before: **we should avoid doing duplicate work.**\n\nIn this case, the work would be duplicated because the *indices* of the partitions don\'t matter - only their *contents* matter.\n\nSo if the *contents* are the same as an earlier partition we tried, skip it.\n\nSimplest example: suppose we\'re placing the first element. Clearly it has to go in some partition. Without loss of generality, let that be `j=0`. So we\'ll place `nums[0]` in `parts[j]`. We\'ll record that we put `nums[0]` in an empty partition. Then, for `j=1..k-1`, we\'ll\n* see that `parts[j]` is also empty\n* and we already tried adding `nums[0]` to an empty partition\n* so we\'ll skip\n\nThat way we don\'t do `N` times as much work as necessary, i.e.\n* putting `nums[0]` in partition `j=0`\n* then retrying with `nums[0]` in partition `j=1`\n* etc.\n\nThe latter partitionings will a permutation of the partitions we got from `nums[0]` in `j=0`. So don\'t explore them again.\n\n## Optimization 3: Only Proceed If We Can Still Improve the Answer\n\nSuppose the current incompatibility is `x`, and the current best answer is `ans`.\n\nIncompatibilty grows over time because we keep putting ever-larger elements in each partition (we sorted `nums`!)\n\nIf `x >= ans` already, then as we finish placing elements, the incompatibility would grow even larger. Anything `>= ans` can\'t improve `ans`, so it\'s wasted work.\n\n**Never spend time on combinations can\'t possibly affect the answer!**\n\nSo we optimize as follows:\n* record the current incompatibility when calling `place`\n* if the current incompatibility is already `>= ans[0]` then return immediately, proceeding would only waste time\n* when placing an element, include the change (increase) in the incompatibility when recursing\n\n**NOTE: this could be improved even more!** There are probably ways to prune search branches along these lines even more effectively. For example, we can "fast-forward" by quickly checking\n* the current partition\'s min value (first value because we sorted `nums` and assign in order)\n* the smallest remaining numbers we can possibly put in the partition\n* if the resulting incompatibility gets us to `>= ans[0]` then we *know* we can\'t improve the answer\n\nBut in an interview I think more elaborate checks like this are too hard... if this problem is already not too hard!!\n\n# Complexity\n- Time complexity: factorial/heinous\n  - depends a LOT on the inputs in particular\n  - but here, in the worst case, we try all combinations of placing each number of copies of each number, which is factorial/combinatorial\n    - so we\'ll try `k choose 0 + ... + k choose f` where `f` is the frequency of value `n`\n    - it\'s all counts because I don\'t have an optimization that forces us to place exactly `f` copies. Oof.\n  - then we\'ll repeat for each later unique value\n  - so we get the *product* of `k choose 0 + .. + k choose f` over all uniques with frequencies `f`\n  - don\'t forget that we do `O(N)` work inside each stack frame too `:(`\n\n- Space complexity: `O(n)`\n  - `n` stack frames\n  - `O(N)` space used for DFS + backtracking structures both inside and outside the `place` method\n\n# Overall\n\n## DFS + Backtracking is Fairly Easy\n\nJust tentatively place an element, explore, then backtrack. Same pattern every time.\n\n## DFS + Backtracking in Practice is Hard\n\nTo avoid TLE, you need to really understand what the recursive calls are doing, and avoid duplicate work.\n\nThis is my ~8th FT 100% solution. Most of those are DFS + backtracking, where I put in optimizations that others haven\'t done before.\n\nSo the secret to performant DFS + backtracking is being *very* careful about avoiding duplicate work:\n* **make sure there\'s only one DFS path leading to each effectively distinct configuration**\n* **prune paths ASAP when you detect they can\'t contribute to the answer**\n  * in this case, "contribute" means "lower the current answer"\n  * in other cases, this can include "adding ways/counts to an overall sum"\n\n# Code\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        # split nums into k subSETS of equal size (N//k) so there are no two equal elements\n        # the incompatibility is the min difference between the max and min elements of a subarray\n\n        # efficiently solving: HARD\n\n        # inefficiently solving: all permutations, 16! is too expensive\n\n        # DFS+bt?\n\n        # quick check to see if a solution is possible at all\n        freqs = Counter(nums)\n        if any(f > k for f in freqs.values()): return -1\n\n        # general idea: assign numbers to partitions in ascending order\n        N = len(nums)\n        nums.sort()\n\n        # we record the values in the partitions, probably not strictly necessary as we\n        # really only need the capacity and min and max, but this is EZ and O(16)\n        parts = [[] for _ in range(k)]\n\n        # key optimization 1: if we\'ve already assigned n to parts[j],\n        # then later place(...) calls should only consider j+1..k-1 so we don\'t duplicate work.\n        # Example: suppose we have k = 8 partitions, and place(i) decided to put n in partition 3\n        #    > that means place(i) explored all combinations resulting from placing n at 0,1,2\n        #    > so place(i+1) with the same n shouldn\'t retry placing at 0,1,2 again\n        #    > this also makes it easy to skip to the next partition that does not have a copy of n\n        # (NOTE: ptr is inspired by Dinic\'s max flow algorithm)\n        ptr = [-1]*17 # most recent partition index we\'ve assigned each number to\n        ans = [math.inf]\n\n        def place(i: int, curr_incompat) -> int:\n            # key optimization 2: early pruning. If current answer isn\'t better, then\n            # the final incompatibility must be at least curr_incompat >= ans[0] so we\n            # can\'t improve the final answer from here\n            #   NOTE: even better pruning is probably possible here, e.g. we know the max\n            #         number (nums[-1]) has to be placed in one of the remaining partitions.\n            #         That will produce a substantial extra incompatibility, and let us more\n            #         quickly rule out partitionings early on that will lead to large\n            #         incompatibilities later\n            if curr_incompat >= ans[0]: return\n\n            if i == N:\n                a = sum(ps[-1] - ps[0] for ps in parts)\n                ans[0] = min(ans[0], a)\n                return\n\n            n = nums[i]\n            p = ptr[n]\n            \n            # key optimization 3: only try distinct destinations. The partitions are *order independent*,\n            # so the actual index j doesn\'t matter: just it\'s contents. So if we\'ve already explored\n            # adding n to a partition with the same contents, just skip it\n            attempted = set()\n            for j in range(p+1, k):\n                if len(parts[j]) == N//k: continue # already full\n\n                state = tuple(parts[j])\n                if state in attempted:\n                    continue\n\n                attempted.add(state) # so we don\'t try a substantially identical target later\n                ptr[n] = j # so recurive calls know we can\'t assign to this partition again\n                parts[j].append(n)\n\n                # if there were no elements before, incompat. didn\'t change, range is still zero\n                delta_incompat = parts[j][-1] - parts[j][-2] if len(parts[j]) >= 2 else 0\n                place(i+1, curr_incompat + delta_incompat)\n\n                # backtrack\n                parts[j].pop()\n\n            # backtrack the ptr change\n            ptr[n] = p\n\n        place(0, 0)\n\n        return ans[0]\n```
['Python3']