C++ | DP | O(n * n * 2^n)
Solution is inspired from following solution [Python] True O(nn2^n) bit dp, explained.\n\nWe try to fill up the dynamic programming table dp[mask][last], where 
Solution is inspired from following solution [[Python] True O(n*n*2^n) bit dp, explained](https://leetcode.com/problems/minimum-incompatibility/discuss/961969/Python-True-O(n*n*2n)-bit-dp-explained).\n\nWe try to fill up the dynamic programming table ```dp[mask][last]```, where it stores minimum incompatibility of elements that are one in ```mask``` and last selected element is ```last```. For example, ```dp[13][2]``` gives minimum incompatibility for selecting 0\'th,2\'nd,3\'rd where last selected element is 2\'nd (13 = 2^0 + 2^2 + 2^3). We know that each group have same number of elements. So, by counting number of set bits in ```mask``` we can know how many elements selected for last group. For example, assume each group should have 2 elements. Then, by looking ```dp[13][2]``` we can say that last group has only [2]. Incompatibility is calculated as max_element - min_element, as it is given in problemt statement. If we select elements of each group in increasing manner, only first and last selected elements affect incompatibility of the group. For example, for ```dp[13][2]``` 2\'nd element is first one for its group, then its incompatibility calculation should have ```-nums[2]```. Also we can know max_element for group when calculating ```dp[mask][last]```. That is, when ```number_of_set_elements_of_mask % group_size == 0```. So we have three cases to calculate ```dp[mask][last]```.\n* if ```number_of_set_elements_of_mask % group_size == 0``` then last element. ```dp[mask][last] = min(dp[prev][last_prev]) + nums[last]``` for all ```last_prev```.\n* if ```number_of_set_elements_of_mask % group_size == 1``` then first element. ```dp[mask][last] = min(dp[prev][last_prev]) - nums[last]``` for all ```last_prev```.\n* else middle elements, which does not have any effect to incompatability calculation. ```dp[mask][last] = min(dp[prev][last_prev])``` for all ```last_prev```.\n\nTime complexity is O(n^2 * n^2). 2^n * n for dp table and n for finding previous best. I think optimization can be done to decrease it to O(n^2 * n).\n\n```\nclass Solution {\npublic:\n    int minimumIncompatibility(vector<int>& nums, int k) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        int INF = nums.back()*n;\n        vector<vector<int>> dp(1<<n, vector<int>(n, INF));\n        vector<int> dp_best(1<<n, INF);\n        int group_size = n/k;\n        \n        if(group_size == 1)\n            return 0;\n        \n        dp_best[0] = 0;\n        \n        int mx = 1<<n;\n        for(int i=1; i<mx; i++){\n            int n_ones = __builtin_popcount(i), mn, prev;\n            \n            for(int j=0; j<n; j++){\n                if(((1<<j) & i) == 0) continue;\n                prev = i^(1<<j);\n\t\t\t\t\n\t\t\t\tif(n_ones % group_size == 1) {// first one\n                    dp[i][j] = dp_best[prev] - nums[j];\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\t\n                mn = INF;\n                for(int p=0; p<j && nums[p]!=nums[j]; p++)\n                    mn = min(mn, dp[prev][p]);\n                \n                if(n_ones % group_size == 0) // last one\n                    dp[i][j] = mn + nums[j];\n                if(n_ones % group_size > 1) // middle ones\n                    dp[i][j] = mn;\n            }\n            \n            for(int j=0; j<n; j++)\n                dp_best[i] = min(dp_best[i], dp[i][j]);\n        }\n        \n        if(dp_best[(1<<n)-1] >= INF)\n            return -1;\n        return dp_best[(1<<n)-1];\n    }\n};\n```\n\nThanks for [@JackyD](https://leetcode.com/JackyD) for suggesting me to make a post for this solution.\n
[]