[C++] Memorization TLE  to AC during contest
Below is the code for which I got TLE\n\nclass Solution {\npublic:\n    int n ,G, INF = 1<<29, K; // G is sizeof subset needed\n    vector<int>nums;\n    vector
Below is the code for which I got TLE\n```\nclass Solution {\npublic:\n    int n ,G, INF = 1<<29, K; // G is sizeof subset needed\n    vector<int>nums;\n    vector<int>freq;\n    int dfs(int idx, int g, int mask, int mini, int maxi) {\n        if (idx >= K) return 0;\n        if (g == G) {\n            return dfs(idx+1, 0, 0, n + 1, 0) + maxi - mini;\n        }\n        \n        int ret = INF;\n        for (int i = 1; i <=n ;i++) if (freq[i] > 0 && (mask&(1<<i)) == 0) {\n            freq[i]--;\n            ret = min(ret, dfs(idx, g + 1, mask |(1<<i), min(mini, i), max(maxi, i)));\n            freq[i]++;\n        }\n        return ret;\n        \n    }\n    int minimumIncompatibility(vector<int>& N, int k) {\n        n = N.size(), K= k;\n        nums = N;\n        G = n/k;\n        freq.resize(n + 1, 0);\n        for (int num : N) freq[num]++;\n        int ans = dfs(0, 0, 0, n + 1, 0);\n        return ans >= INF ? -1: ans;\n    }\n};\n```\nAfter TLE  I realised we can precompute the valid mask and can run the dfs on same. Below is the solution for same\n```\nclass Solution {\npublic:\n    int n, K, INF = 1<<29;\n    vector<int>nums;\n    vector<pair<int, int>>validMask;\n    int memo[17][(1<<16) + 10];\n    bool isValid(int mask) {\n        unordered_map<int, bool> seen;\n        for (int i =0 ; i < n; i++) {\n            if (mask&(1<<i) ) {\n                if (seen.count(nums[i])) return false;\n                seen[nums[i]] = true;\n            }\n        }\n        return true;\n    }\n    int solve(int idx, int mask) {\n        if (idx == K) return 0;\n        if (memo[idx][mask] != -1) return memo[idx][mask];\n        int ret = INF;\n        for (auto m : validMask) if ((m.first&mask) == 0){\n            ret = min(ret, solve(idx + 1, mask|m.first) + m.second);\n        }\n        return memo[idx][mask] = ret;\n    }\n    int getMin(int mask) {\n        int mini = n + 1;\n        for (int i =0 ; i < n; i++) if (mask&(1<<i) ) mini = min(mini, nums[i]);\n        return mini;\n    }\n    int getMax(int mask) {\n        int maxi = 0;\n        for (int i =0 ; i < n; i++) if (mask&(1<<i) ) maxi = max(maxi, nums[i]);\n        return maxi;\n    }\n    int minimumIncompatibility(vector<int>& N, int k) {\n        nums = N, K = k;\n        n = nums.size();\n        int G = n /k;\n        for (int i = 0; i < (1<<n); i++) {\n            int c =0;\n            for (int j =0 ; j < n; j++) if (i&(1<<j)) c++;\n            if (c == G && isValid(i)) validMask.push_back({i, getMax(i)- getMin(i)});\n        }\n        int m = validMask.size();\n        memset(memo, -1, sizeof(memo));\n        int ans = solve(0, 0);\n        return ans >= INF ? -1 : ans;\n    }\n};\n```
['Memoization', 'C', 'Bitmask']