C++ version backtrack with "visited set" modified from Java with comments
This is really a hard one to understand... Personally I don\'t like the bitmask-type question, which is rarely in real interview.\nI am glad to see solution don
This is really a hard one to understand... Personally I don\'t like the bitmask-type question, which is rarely in real interview.\nI am glad to see solution done by @pigorski. I read that solution and write my own C++ version here, with a bit optimization (maybe?). Please see comments.\n\nlink to original [solution by pigorski](https://leetcode.com/problems/minimum-incompatibility/discuss/961470/Java-backtrack-solution-with-optimizations)\n\n```\nclass Solution {\npublic:\n    // put index into sets\n    void dfs(int index, int m, int csum, int & res, vector<int>& nums, vector<vector<int>> & sets) {\n        if (csum > res) {\n            return; // early terminate, if cost already over current best solution\n        }\n        if (index == nums.size()) { // all values from nums have been allocated, time to update final solution\n            res = min(res, csum);\n            return;\n        }\n        \n        set<vector<int>> visited; \n\t\t// we dont need to put nums[index] into the same set\n\t\t// For example, if current sets include [[0, 1], [0, 1]], we only need to update [[0, 1, 2] [0, 1]], \n\t\t// no need to do [[0, 1][0,1, 2]]\n        \n        for (int i = 0; i < sets.size(); ++i) {\n            if (visited.count(sets[i])) {\n                continue;\n            }\n            visited.insert(sets[i]);\n\n            if (sets[i].empty()) { // for empty set, we always put value inside, no change to total cost\n                sets[i].push_back(nums[index]);\n                dfs(index + 1, m, csum, res, nums, sets);\n                sets[i].pop_back();\n            } else {\n                if (sets[i].back() >= nums[index] || sets[i].size() == m) { \n\t\t\t\t    // every number must be larger than the previous one, this might be an optimization. Simplify difference\n\t\t\t\t\t// calculation and avoid duplicates.\n                    continue;\n                }\n                int last = sets[i].back();\n                int diff = (nums[index] - last); // increment to total incompatibility\n\n                sets[i].push_back(nums[index]);\n                dfs(index + 1, m, csum + diff, res, nums, sets);\n                sets[i].pop_back();                \n            }\n        }\n        \n    }\n    \n    int minimumIncompatibility(vector<int>& nums, int k) {\n        int n = nums.size(); // [1,n]\n        vector<int> count(nums.size() + 1);\n        int maxl = 0;\n        for (int i: nums) {\n            count[i]++;\n            maxl = max(maxl, count[i]);\n        }\n        if (maxl > k) {\n            return -1;\n        }\n        int m = n / k; // length for each\n        vector<vector<int>> sets(k); // k empty sets\n        sort(begin(nums), end(nums));\n        int res = INT_MAX;\n        \n        dfs(0, m, 0, res, nums, sets);\n        \n        return res == INT_MAX ? -1 : res;\n    }\n};\n```
[]