[C++] Backtracking Solution
Code\ncpp []\nclass Solution {\npublic:\n    int maxVal, n, m;\n    unordered_map<string, int> memo;\n\n    string createKey(int row, const set<int>& usedValues
# Code\n```cpp []\nclass Solution {\npublic:\n    int maxVal, n, m;\n    unordered_map<string, int> memo;\n\n    string createKey(int row, const set<int>& usedValues) {\n        string key = to_string(row) + "|";\n        for (int value : usedValues) {\n            key += to_string(value) + ",";\n        }\n        return key;\n    }\n\n    void dfs(vector<vector<int>>& grid, int row, int currentScore, set<int> usedValues, vector<int>& possibleValues) {\n        maxVal = max(maxVal, currentScore);\n        if (row == n) {\n            return;\n        }\n\n        string key = createKey(row, usedValues);\n        if (memo.count(key)) {\n            maxVal = max(maxVal, memo[key]);\n            return;\n        }\n\n        // Pruning: skip if the potential gain is smaller than the current maxVal.\n        if (currentScore + possibleValues[row] <= maxVal) return;\n\n        for (int col = 0; col < m; col++) {\n            int value = grid[row][col];\n            if(!usedValues.count(value)) {\n                usedValues.insert(value);\n                dfs(grid, row + 1, currentScore + value, usedValues, possibleValues);\n                usedValues.erase((usedValues.find(value)));\n            } else {\n                 dfs(grid, row+1, currentScore, usedValues, possibleValues);\n            }\n        }\n\n        // Store the result in memo\n        memo[key] = maxVal;\n    }\n\n    int maxScore(vector<vector<int>>& grid) {\n        n = grid.size();\n        m = grid[0].size();\n        maxVal = INT_MIN;\n\n        for (int i = 0; i < n; i++) {\n            sort(grid[i].rbegin(), grid[i].rend());\n        }\n\n        sort(grid.rbegin(), grid.rend());\n\n        vector<int> possibleValues(n, 0);\n        possibleValues[n-1] = grid[n-1][0]; \n        for (int i = n-2; i >= 0; i--) {\n            possibleValues[i] = possibleValues[i+1] + grid[i][0];\n        }\n        set<int> usedValues;\n        dfs(grid, 0, 0, usedValues, possibleValues);\n\n        return maxVal;\n    }\n};\n\n```
['C++']