[C++] Bitmask DP with Preprocessing
\nclass Solution {\npublic:\n#define MAXN (1<<17)\nint f[MAXN];\nint g[17];\nint NR[MAXN];\nvector<vector<int>> vii;\nvoid decode (int state, int n){\n        i
```\nclass Solution {\npublic:\n#define MAXN (1<<17)\nint f[MAXN];\nint g[17];\nint NR[MAXN];\nvector<vector<int>> vii;\nvoid decode (int state, int n){\n        int q = 0;\n        for(int i = 0; i < n; ++i)\n            if((state & (1<<i)) == 0)\n                g[++q] = i;\n        g[0] = q;\n        return ;\n} \n\nvector<vector<int>> enumerate(vector<int> & nums, int n, int k, int depths, int pos){\n    if(depths == k){\n        vector<vector<int>> a;\n        a.push_back(vector<int>());\n        return a;\n    }\n    vector<vector<int>> ret;\n    for(int i = pos; i < n; ++i){\n        vector<vector<int>> vi = enumerate(nums, n ,k , depths + 1, i + 1);\n        for(auto x : vi){\n            vector<int> b = x;\n            b.push_back(i);\n            bool flag = true;\n            int mm = b.size();\n            for(int v = 0; v < mm; ++v)\n                for(int w = 0; w < mm; ++ w)\n                    if(nums[b[v]] == nums[b[w]] && v != w)\n                        flag = false;\n            if(flag)\n                ret.push_back(b);\n            \n        }\n    }\n    if(depths != 0){\n        return ret;\n    }else{\n        vector<vector<int>> finalized;\n        for(int j = 0; j < ret.size(); ++j){\n            bool flag = true;\n            if(flag)\n                finalized.push_back(ret[j]);\n        }\n        return finalized;\n    }\n}\nint getmaxmin(vector<int> & nums, vector<int> & x, int k){\n    int mmax = nums[x[0]], mmin = nums[x[0]];\n    for(int i = 0; i < k; ++i)\n    {\n        mmax = max(nums[x[i]], mmax);\n        mmin = min(nums[x[i]], mmin);\n    }\n    return mmax - mmin;\n}\nint dfs(int state, vector<int>& nums, int n, int k){\n    if(state == ((1<<n)-1))\n        return 0;\n    if(f[state] != -2){\n        return f[state];\n    }\n    decode(state, n);\n    int ans = -1;\n    for(int i = 0; i < vii.size(); ++i){\n        if(NR[i] & state) continue;\n        int newstate = state | NR[i];\n        int m = getmaxmin(nums, vii[i], k);\n        if (m > ans && ans != -1) continue;\n        int p = dfs(newstate, nums, n, k);\n        if (p == -1)\n            continue;\n        if ( ans == -1 || ans > m+p){\n            ans = m + p;\n        }\n    }\n    f[state] = ans;\n    return ans;\n}\n\nint minimumIncompatibility(vector<int>& nums, int k) {\n    int n = nums.size();\n    vii = enumerate(nums,  n,n/k, 0, 0);\n    for(int i = 0; i < vii.size(); ++i){\n        for(int j = 0; j < vii[i].size(); ++ j)\n            NR[i] |= (1<<vii[i][j]);\n    }\n    for(int i = 0; i<= ((1<<n)-1); ++i){\n        f[i] = -2;\n    }\n    return dfs(0,nums, n, n/k);\n}\n};\n```
[]