1681. Minimum Incompatibility
Intuition\nThe problem asks to distribute the elements of an array into k subsets such that each subset has no duplicate elements and the sum of their incompati
# Intuition\nThe problem asks to distribute the elements of an array into `k` subsets such that each subset has no duplicate elements and the sum of their incompatibilities (difference between the maximum and minimum elements) is minimized. The first thought is that we can try to form all possible valid subsets of equal size and compute their incompatibilities. Using dynamic programming, we can then find an optimal way to partition the array into these subsets.\n\n# Approach\n1. Check for duplicates: If any element appears more than `k` times in the array, it is impossible to distribute the elements into `k` subsets without duplicates, so return `-1`.\n2. Subset incompatibility calculation: Generate all possible subsets of the array and calculate the incompatibility for subsets that contain exactly `n/k` elements. Ensure that these subsets do not contain duplicates.\n3. Dynamic Programming: Use dynamic programming to find the minimum incompatibility sum. We use a bitmask to represent different subsets. For each possible mask, compute its smaller valid subsets and update the DP table by adding the incompatibility of those subsets while ensuring no integer overflow occurs.\n\n# Complexity\n- Time complexity:\nThe time complexity is \uD835\uDC42(2\uD835\uDC5B\xD7\uD835\uDC5B), where n is the number of elements in the array. This is because we generate all subsets of the array (which is 2\uD835\uDC5B subsets) and for each subset, we may need to check or sort its elements.\n- Space complexity:\nThe space complexity is \uD835\uDC42(2\uD835\uDC5B) since we maintain a DP array and a subset incompatibility array, both of size 2\uD835\uDC5B. Additionally, sorting subsets in each iteration can use additional space but is still dominated by the DP table size.\n# Code\n```cpp []\n#include <vector>\n#include <unordered_map>\n#include <algorithm>\n#include <climits>\n\nclass Solution {\npublic:\n    int minimumIncompatibility(std::vector<int>& nums, int k) {\n        int n = nums.size();\n        int subsetSize = n / k;\n\n        std::unordered_map<int, int> freq;\n        for (int num : nums) {\n            freq[num]++;\n            if (freq[num] > k) {\n                return -1;\n            }\n        }\n\n        int totalSubsets = 1 << n; \n        std::vector<int> subsetIncompatibility(totalSubsets, INT_MAX);\n        std::vector<int> dp(totalSubsets, INT_MAX);\n        dp[0] = 0;\n\n        for (int subset = 0; subset < totalSubsets; subset++) {\n            std::vector<int> elements;\n            for (int i = 0; i < n; i++) {\n                if (subset & (1 << i)) {\n                    elements.push_back(nums[i]);\n                }\n            }\n            if (elements.size() == subsetSize) {\n                std::sort(elements.begin(), elements.end());\n                bool valid = true;\n                for (int i = 1; i < elements.size(); i++) {\n                    if (elements[i] == elements[i - 1]) {\n                        valid = false;\n                        break;\n                    }\n                }\n                if (valid) {\n                    subsetIncompatibility[subset] = elements.back() - elements.front();\n                }\n            }\n        }\n\n        for (int subset = 0; subset < totalSubsets; subset++) {\n            if (__builtin_popcount(subset) % subsetSize == 0) {\n                for (int smallerSubset = subset; smallerSubset; smallerSubset = (smallerSubset - 1) & subset) {\n                    if (subsetIncompatibility[smallerSubset] != INT_MAX && dp[subset ^ smallerSubset] != INT_MAX) {\n                        \n                        if (dp[subset ^ smallerSubset] <= INT_MAX - subsetIncompatibility[smallerSubset]) {\n                            dp[subset] = std::min(dp[subset], dp[subset ^ smallerSubset] + subsetIncompatibility[smallerSubset]);\n                        }\n                    }\n                }\n            }\n        }\n\n        return dp[totalSubsets - 1] == INT_MAX ? -1 : dp[totalSubsets - 1];\n    }\n};\n\n```
['C++']