Python backtracking code with comments
Mixture of two backtracking approaches. \n [Python] simple backtracking beats 100%\n\n Java backtrack solution with optimizations\n\n\n\nclass Solution:\n    de
Mixture of two backtracking approaches. \n* [[Python] simple backtracking beats 100%\n](https://leetcode.com/problems/minimum-incompatibility/discuss/961470/Java-backtrack-solution-with-optimizations)\n* [Java backtrack solution with optimizations](https://leetcode.com/problems/minimum-incompatibility/discuss/961470/Java-backtrack-solution-with-optimizations)\n\n\n```\nclass Solution:\n    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n        d = len(nums) // k\n        nums = sorted(nums, reverse=True)\n        \n        part = [[] for _ in range(k)]\n        self.res = float(\'inf\')\n        \n        def calc():\n            # Calculate incompatability score from all partitions\n            score = 0\n            for l in part:\n                if len(l) <= 1:\n                    continue\n                score += (l[0] - l[-1])\n            return score\n        \n        def assign(i):\n            if i == len(nums):\n                self.res = min(self.res, calc())\n                return\n            \n            visited = set()\n            for j in range(k):\n                if len(part[j]) == d or (len(part[j]) > 0 and part[j][-1] == nums[i]) or (tuple(part[j]) in visited):\n                    # Already full or previous element is identical or duplicate partition\n                    continue\n                \n                # Not to test same partition again and again\n\t\t\t\t# [[1], [], []] is same as [[], [1], []]\n                visited.add(tuple(part[j]))\n                \n                part[j].append(nums[i])\n                if calc() < self.res:\n                    assign(i+1)\n                part[j].pop()\n            return\n        \n        assign(0)\n        return -1 if self.res == float(\'inf\') else self.res           \n```\n\n`Should also pass: nums=[10,10,9,9,8,8,8,8,2,1], k=5`\n\n### Optimization ideas\n* Used sorted nums list for easier cacluation of Incompatibility\n* Early break on ongoing total score exceeds current minimum complete total score\n* Visited set for not visiting duplicate partiton in different position
['Backtracking', 'Python']