Generate all subsets and Backtracking
It took me a lot of time to understand the bitmask solution. I think it would be easier to pre-generate all possible subsets and then try backtracking with prun
It took me a lot of time to understand the bitmask solution. I think it would be easier to pre-generate all possible subsets and then try backtracking with pruning.\n\n# Approach\n1. Using bitmask to generate all possible groups, and caculate the incompability score of each group. Number of groups <= C(n, n/k).\n2. Try possibile combinations of these groups, maintain a `remain` to track indexes have not be used. \n\n# Code\n```\nclass Solution {\npublic:\n    int minimumIncompatibility(vector<int>& nums, int k) {\n        int n = nums.size();\n        int groupSize = n/k;\n\n        unordered_map<int, int> allGroups; // all groups of size == groupSize\n        unordered_map<int, int> memo;\n\n        sort(nums.begin(), nums.end()); // sort the array make it easier to find duplicated number\n        generateAllGroups(allGroups, groupSize, nums);\n\n        return findMinScore(0, k, (1 << n) - 1, allGroups, memo);\n    }\n\n    int findMinScore(int i, int groups, int remain, unordered_map<int, int> &allGroups, unordered_map<int, int>& memo) {\n        if (i == groups) return 0;\n        if (memo.contains(remain)) return memo[remain];\n        \n        int minScore = INT_MAX;\n\n        for (auto &g : allGroups) {\n            if ((g.first & remain) == g.first) { // if remaining indexes include all the indexes in current group\n                remain -= g.first;\n\n                int score = findMinScore(i+1, groups, remain, allGroups, memo);\n\n                if (score != -1) {\n                    minScore = min(minScore, g.second + score);\n                }\n\n                remain += g.first;\n            }\n        }\n\n        memo[remain] = minScore == INT_MAX ? -1 : minScore;\n    \n        return memo[remain];\n    }\n\n    void generateAllGroups(unordered_map<int, int> &allGroups, int groupSize, vector<int>& nums) {\n        int n = nums.size();\n\n        // for simplicity, we check all the combinations\n        for (int i = 0; i < (1 << n); ++i) {\n            int bits = 0;\n            int minVal = INT_MAX;\n            int maxVal = INT_MIN;\n\n            for (int j = 0, k = -1; j < n; ++j) {\n                if (i & (1 << j)) {\n                    if (k != -1 && nums[j] == nums[k]) { // same number, invalid group\n                        bits = 0;\n                        break;\n                    }\n\n                    bits++;\n                    minVal = min(minVal, nums[j]);\n                    maxVal = max(maxVal, nums[j]);\n                    k = j;\n                }\n            }\n\n            if (bits == groupSize) {\n                allGroups[i] = maxVal - minVal;\n            }\n        }\n    }\n};\n```
['C++']