Hall's Marriage Theorem (Beats 100% Time and Memory Complexity)
Approach\nFor each unique value, find out the set of rows it\'s located on (we can store using this bitmask; here I save it in the pos array). \n\nNow model the
# Approach\nFor each unique value, find out the set of rows it\'s located on (we can store using this bitmask; here I save it in the `pos` array). \n\nNow model the problem as a bipartite graph, the left one containing the values, and the right one containing the rows. We connect two vertices `(v, r)` if the value `v` exists in the row `r`. Surely, we can use maxflow for graph matching to solve the problem, but we can also use Hall\'s marriage theorem. In order for a matching to exist, the following marriage condition is necessary and sufficient:\n\nFor each set of values $S_v$, the union of the set of rows in which they exist must be larger than or equal to the size of $S_v$. (i.e. if we select any set of vertices on the left, the number of the vertices on the right which is adjacent to at least one selected vertiex on the left must be larger).\n\nTo apply this, we greedily try to select the values from the largest to smallest (iterate $i$ from $100$ to $1$). Let $ve$ be the currently selected values. To check the marriage condition, we iterate over the subset of $ve$ appended with $i$. If the marriage condition is satisfied for every subset, then we insert $i$ to $ve$. Once the size of $ve$ reaches the number of rows, we can just exit the loop and return the sum of the selected numbers.\n\n# Complexity\n- Time complexity:\n$O(V \\times 2^{N} \\times N)$\n\n- Space complexity:\n$O(V + N)$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        int pos[101];\n        memset(pos, 0, sizeof(pos));\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                pos[grid[i][j]] |= (1 << i);\n            }\n        }\n        int ve[10];\n        int sz = 0;\n        int ret = 0;\n        for (int i = 100; i >= 0; i--) {\n            if (pos[i] == 0) continue;\n            bool ok = true;\n            for (int j = 0; j < (1 << sz); j++) {\n                int tmp = pos[i];\n                int cnt = 1 + __builtin_popcount(j);\n                for (int k = 0; k < sz; k++) {\n                    if ((j >> k) & 1) { tmp |= pos[ve[k]]; }\n                }\n                if (__builtin_popcount(tmp) < cnt) {\n                    ok = false;\n                    break;\n                }\n            }\n            if (!ok) continue;\n            ve[sz++] = i;\n            ret += i;\n            if (sz >= m) {\n                break;\n            }\n        }\n        return ret;\n    }\n};\n```
['C++']