python short dfs solution | value-based bitmask
Note all nums[i]<16, we can directly use bitmask to represent the values used in each subset.\nPruning condition discussed in this solution will be more efficie
Note all nums[i]<16, we can directly use bitmask to represent the values used in each subset.\nPruning condition discussed in [this solution](https://leetcode.com/problems/minimum-incompatibility/discuss/961672/Python-DFS-backtracking-pruning-(~100-ms)) will be more efficient with a single mask value.\n```\nWith this bitmask, we can efficiently check the following condion\n1. same combination   --> check value of mask\n2. avoid duplicate number  -->  check whether the bit in mask is 1 \n3. bag is full  --> check number of 1 in mask\n```\n\n```\ndef minimumIncompatibility(self, nums: List[int], k: int) -> int:\n\tif max(Counter(nums).values())>k:\n\t\treturn -1\n\tnums, mask, ans = sorted(nums), [0]*k, max(nums)*k\n\n\tdef score(m):\n\t\tmx = int(log2(m))   # leftmost 1\'s location - max value\n\t\tmn = int(log2(m&-m)) # rightmost 1\'s location - min value\n\t\treturn mx-mn\n\n\tdef dfs(i, j, ans):\n\t\tif sum(score(m) for m in mask if m)+len(nums) - j - sum(not m for m in mask) >= ans:\n\t\t\treturn ans\n\t\t# each unassigned num will increase incompatibility at least by 1\n\n\t\tif j==len(nums):\n\t\t\treturn sum(score(m) for m in mask)\n\t\tfor i in range(k):\n\t\t\tif mask[i].bit_count()<len(nums)//k and (not mask[i]&(1<<nums[j])) and (not i or mask[i-1] != mask[i]):\n\t\t\t\tmask[i] |= (1<<nums[j])   # add nums[j] in mask[i]\n\t\t\t\tans = dfs(i, j+1, ans)\n\t\t\t\tmask[i] ^= (1<<nums[j])  # remove nums[j] in mask[i]\n\t\treturn ans\n\n\treturn dfs(0, 0, ans)\n```
[]