C++ DP with explanation and comments
Since n is at most 16, we can use a bitmap to represent any subset of the input array. Define dp[b] as the answer to the subset represented by bitmap b, we can 
Since n is at most 16, we can use a bitmap to represent any subset of the input array. Define `dp[b]` as the answer to the subset represented by bitmap `b`, we can iterate over all the valid subset `tb` of `b` of size `n/k`, and update `dp[b]` as `min(dp[b], dp[b-tb]+dp[tb])`.\n\nTo speed up the inner loop, we can pre-generate all the valid subsets of size `n/k` and corresponding incompatibilities.\n\n**Original Solution:**\n```\nclass Solution {\npublic:\n    int minimumIncompatibility(vector<int>& nums, int k) {\n        const int n = nums.size(), m = n/k;\n        const vector<pair<int, int>> bmap = getMap(nums, m);\n\n        vector<int> dp(1<<n, -1);\n        dp[0] = 0;\n        for (int b = 0; b < (1<<n); ++b) {\n            if (__builtin_popcount(b) % m != 0) continue;\n            for (const auto& [tb, v] : bmap) {\n                if (tb > b) break; // Only try m-digit combinations smaller than b.\n                if ((tb & b) != tb) continue;\n                if (dp[b-tb] == -1) continue;\n                if (dp[b] == -1) dp[b] = dp[b-tb]+v;\n                else dp[b] = min(dp[b], dp[b-tb]+v);\n            }\n        }\n        return dp.back();\n    }\n\nprivate:\n    // Pre-generates all valid subsets and corresponding incompatibilities.\n    vector<pair<int, int>> getMap(const vector<int>& nums, int m) {\n\t    const int n = nums.size();\n        vector<pair<int, int>> ans;\n        for (int b = 0; b < (1<<n); ++b) {\n            if (__builtin_popcount(b) != m) continue;\n\n            int vis = 0;\n            int mx = 0, mn = 16;\n            bool is_good = true;\n            for (int i = 0; i < n; ++i) {\n                if ((b & (1<<i)) == 0) continue;\n                if (vis & (1<<nums[i])) {\n                    is_good = false;\n                    break;\n                }\n                vis |= (1<<nums[i]);\n                mx = max(mx, nums[i]);\n                mn = min(mn, nums[i]);\n            }\n            if (!is_good) continue;\n            \n            ans.emplace_back(b, mx-mn);\n        }\n        return ans;\n    }\n};\n```\n\n**Optimization (credit to [@apluscs](https://leetcode.com/apluscs/))**\nInstead of interating over `bmap` in the innner loop, we can iterate over all the sub-bitmasks of `b` instead. (See details in @apluscs\'s great [comment](https://leetcode.com/problems/minimum-incompatibility/discuss/961451/C++-DP-with-explanation-and-comments/782104) below).\n```\nclass Solution {\npublic:\n    int minimumIncompatibility(vector<int>& nums, int k) {\n        const int n = nums.size(), m = n/k;\n        const vector<int> bmap = getMap(nums, m);\n\n        vector<int> dp(1<<n, -1);\n        dp[0] = 0;\n        for (int b = 0; b < (1<<n); ++b) {\n            if (__builtin_popcount(b) % m != 0) continue;\n\t\t\t// Reference: https://cp-algorithms.com/algebra/all-submasks.html\n            for (int tb = b; tb; tb = (tb-1)&b) {\n                if (bmap[tb] == -1) continue;\n                if (dp[b-tb] == -1) continue;\n                if (dp[b] == -1) dp[b] = dp[b-tb]+bmap[tb];\n                else dp[b] = min(dp[b], dp[b-tb]+bmap[tb]);\n            }\n        }\n        return dp.back();\n    }\n\nprivate:\n    // Generates a vetor v where:\n    //   v[b] = the incompatibility of bitmask b, if b represents a valid subset of size m\n    //   v[b] = -1, if b is not a valid subset of size m\n    vector<int> getMap(const vector<int>& nums, int m) {\n\t    const int n = nums.size();\n        vector<int> ans(1<<n, -1);\n        for (int b = 0; b < (1<<n); ++b) {\n            if (__builtin_popcount(b) != m) continue;\n\n            int vis = 0;\n            int mx = 0, mn = 16;\n            bool is_good = true;\n            for (int i = 0; i < n; ++i) {\n                if ((b & (1<<i)) == 0) continue;\n                if (vis & (1<<nums[i])) {\n                    is_good = false;\n                    break;\n                }\n                vis |= (1<<nums[i]);\n                mx = max(mx, nums[i]);\n                mn = min(mn, nums[i]);\n            }\n            if (!is_good) continue;\n            \n            ans[b] = mx-mn;\n        }\n        return ans;\n    }\n};\n```
[]