[Python] True O(n*n*2^n) bit dp, explained
I saw a lot of solutions here, which state that they have complexity O(n*2^n), but without really explaining why it is true. Here is my implementation, using bi
I saw a lot of solutions here, which state that they have complexity `O(n*2^n)`, but without really explaining why it is true. Here is my implementation, using bitmask, which is similar to TSE problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem): we need to keep state in the form: `bitmask, last`, where:\n1. `bitmask` is bitmask for all numbers already taken.\n2. `last` is index of last taken number.\n\nHow are we going to form our groups: sort our numbers first and imagine we have numbers `[1,1,2,3,3,4]`: and `k = 3`. Then we need to create first group of `2` elements, for example it can be elements with indexes `1,2`, and we have current bitmask `011000`, then we need to form another group of `2` elements, for example it can be elements with indexes `0,5`, so we have bitmask `111001` now. Finally we put last two elements in last group. We can interpret it as TSE problem: we choose path `1->2->0->5->3->4`.  Note, that in each group we only choose increasing indexes, whereas between groups than can decrease (but can increase also).\n\nNow, what we have in our algorithm:\n1. We iterate over all possible `mask`\n2. Calculate places, where we have `1` in this mask.\n3. Now, we can have two cases: first, if `len(n_z_bits)%(n//k) == 1`: it means, that it is time to start new group, so we can choose any index we want, not neccecerily bigger than previous, so we choose `permutations` here: there will be exactly `t(t-1)/2` pairs and for each of them we update `dp[mask][l]`.\n4. In other case, it means, that we need to continue to build our group, so next index should be bigger than previous and we choose `combinations` here. Also we check that new number is not equal to last one we have and again update `dp[mask][l]`.\n5. Finally, we return minimum from `dp[-1]`.\n\n**Complexity**: time complexity is `O(n*n*2^n)` as TSE have: we have `2^n` bitmasks and we have `O(n^2)` time to process each mask. In python it is working not very fast, I can say it is barely accepted, so, I think there should be `O(n*2^n)` solution as well, if you know such solution (desirebly with explanations), please let me know!\n\n```python\nclass Solution:\n    def minimumIncompatibility(self, nums, k):\n        n = len(nums)\n        if k == n: return 0\n        dp = [[float("inf")] * n for _ in range(1<<n)] \n        nums.sort()\n        for i in range(n): dp[1<<i][i] = 0\n\n        for mask in range(1<<n):\n            n_z_bits = [j for j in range(n) if mask&(1<<j)]\n            if len(n_z_bits)%(n//k) == 1:\n                for j, l in permutations(n_z_bits, 2):\n                    dp[mask][l] = min(dp[mask][l], dp[mask^(1<<l)][j])\n            else:\n                for j, l in combinations(n_z_bits, 2):\n                    if nums[j] != nums[l]:\n                        dp[mask][j] = min(dp[mask][j], dp[mask^(1<<j)][l] + nums[l] - nums[j])\n                        \n        return min(dp[-1]) if min(dp[-1]) != float("inf") else -1\n```\n\n**PS**: leetcode changed their tests, so I also need to adjust my code a bit. Complexity is still the same, but now it is working 9800-9950 milliseconds, so barely passes =)\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]