C++ | Top Down | 2^n * n *n | TLE
Getting the message 56 / 56 test cases passed, but took too long. after submission.\n\n\n    \n    int find(int i, int j, vector &nums, int n, int k, vector >&d
Getting the message `56 / 56 test cases passed, but took too long.` after submission.\n\n\n    \n    int find(int i, int j, vector<int> &nums, int n, int k, vector<vector<int> >&dp) {\n        \n        int setBits = 0;\n        int temp = i;\n        while (temp > 0) {\n            if (temp % 2 != 0)\n                setBits ++;\n            temp = temp/2;\n        }\n        \n        if (setBits == n)\n        {\n            return 0;\n        }\n    \n        \n        if( j >= n)\n            return INT_MAX;\n        \n        if(dp[i][j] != -1)\n            return dp[i][j];\n        \n        int ans = INT_MAX;\n        int x = j;\n        \n        int numberOfElementsInCurrentSubset = setBits % (n/k) ;\n        while (x < nums.size()) {\n            \n            if ( (i & (1 << x)) != 0) {\n                x++;\n                continue;\n            }\n            \n            int newX = x+1;\n            while(newX < nums.size() && nums[x] == nums[newX]) {\n                newX++;\n            }\n            \n            \n            ans = min(ans, find(i, newX, nums, n, k, dp));\n            if(numberOfElementsInCurrentSubset == 0) {\n                int val =  find ( i | (1 << x), newX, nums, n, k,  dp);\n                \n                if(val != INT_MAX)\n                    ans = min (ans, (-1*nums[x]) + val);\n                \n            } else if(numberOfElementsInCurrentSubset == ((n/k)-1)) {\n                int val =  find(i | ( 1 << x), 0, nums, n, k, dp);\n                \n                if (val != INT_MAX)\n                    ans = min(ans, nums[x] + val);\n                \n            } else {\n                int val =  find ( i | (1 << x), newX, nums, n, k,  dp);\n                \n                if(val != INT_MAX)\n                    ans = min (ans, val);\n\n            }\n            \n            x = newX; \n        }\n        \n        dp[i][j] = ans;\n        \n        return dp[i][j];\n        \n    }\n    \n    int minimumIncompatibility(vector<int>& nums, int k) {\n        if(nums.size() % k != 0 )\n            return -1;\n        if( (nums.size() / k) == 1)\n            return 0;\n        vector<vector<int> > dp(pow(2, 17), vector<int>(17, -1));\n        sort(nums.begin(), nums.end());\n \n        \n        int ans = find(0, 0, nums, nums.size(), k, dp);\n        if(ans == INT_MAX)\n            return -1;\n        return ans;\n    }\n
[]