1681. Minimum Incompatibility.cpp
Code\n\nclass Solution {\npublic:\n    int minimumIncompatibility(std::vector<int>& nums, int k) {\n        int n = nums.size();\n        int subsetSize = n / k
**Code**\n```\nclass Solution {\npublic:\n    int minimumIncompatibility(std::vector<int>& nums, int k) {\n        int n = nums.size();\n        int subsetSize = n / k;\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        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        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        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                        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        return dp[totalSubsets - 1] == INT_MAX ? -1 : dp[totalSubsets - 1];\n    }\n};\n\n```
['C']