Backtracking with pruning
Intuition\n Describe your first thoughts on how to solve this problem. \nThe requirement to have an element from every row implies that there has to be atleast 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe requirement to have an element from every row implies that there has to be atleast 1 unique element per row, and if that element has to be selected from that row it can\'t be selected from another row.\nWith the above condition in mind we can split every row into 2 types, where only a unique element is present, and where more than 1 unique elements are present.\nFor every row with a unique element select that element first and remove it from every other row.\nIf there are no rows with a single unique element we should then select the maximum element from the remaining grid. As selecting any other element gives a sub-optimal answer read [this solution](https://leetcode.com/problems/select-cells-in-grid-with-maximum-score/solutions/5718057/python-java-dfs-in-descending-orders-with-detailed-explanation) for detailed explanation of the same logic.\nAnd get the solution by removing each row once and checking for the maximum answer.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nA key trick with this solution is to see that when selecting the maximum\nelement from a row, we don\'t select other rows that are exactly equal (as in rows that contain the same set of inputs)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO((m*n^3)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m*n^2)\n# Code\n```java []\nclass Solution {\n    record Element(int k, Queue<Integer> q) {}\n    public int maxScore(List<List<Integer>> grid) {\n        Map<Integer,Set<Integer>> nums = new HashMap<>();\n        int counter=0;\n        for(List<Integer> l : grid) {\n            nums.put(counter++, new HashSet<>(l));\n        }\n        return maxScore(nums);\n    }\n    int maxScore(Map<Integer, Set<Integer>> grid) {\n        if(grid.size()==0) return 0;\n        int singleton = -1;\n        for(int key : grid.keySet()) {\n            if(grid.get(key).size()==1) {\n                singleton=key;\n                break;\n            }\n        }\n        if(singleton==-1) {\n            //Todo: Get max element, remove it from every other set, pass to maxScore\n            int max = 0;\n            List<Integer> candidates = new ArrayList<>();\n            for(int k: grid.keySet()) {\n                Set<Integer> s = grid.get(k);\n                for(int i : s) {\n                    if(max<i) {\n                        max=i;\n                        candidates.clear();\n                        candidates.add(k);\n                    } else if(max==i) {\n                        candidates.add(k);\n                    }\n                }\n            }\n            int result = max;\n            List<Integer> finalCandidates = new ArrayList<>();\n            Set<Set<Integer>> seen = new HashSet<>();\n            for(int c : candidates) {\n                Set<Integer> x = grid.get(c);\n                x.remove(max);\n                if(!seen.contains(x)) {\n                    finalCandidates.add(c);\n                    seen.add(x);\n                }\n            }\n            int rMax = 0;\n            for(int c: finalCandidates) {\n                Set<Integer> temp = grid.get(c);\n                grid.remove(c);\n                int tscore = maxScore(deepCopy(grid));\n                rMax=Math.max(rMax, tscore);\n                grid.put(c, temp);\n            }\n            return result+rMax;\n        } else {\n            //Todo: Get the element from singleton and remove it from every other set\n            //Remove all empty sets and singleton and pass to maxScore\n            int element = grid.get(singleton).iterator().next();\n            grid.remove(singleton);\n            for(Set<Integer> s : grid.values()) {\n                s.remove(element);\n            }\n            List<Integer> toRemove = new ArrayList<>();\n            for(int k: grid.keySet()) {\n                if(grid.get(k).size()==0) {\n                    toRemove.add(k);\n                }\n            }\n            for(int k : toRemove) {\n                grid.remove(k);\n            }\n            return element + maxScore(deepCopy(grid));\n        }\n    }\n    Map<Integer, Set<Integer>> deepCopy(Map<Integer, Set<Integer>> orig) {\n        Map<Integer, Set<Integer>> res = new HashMap<>();\n        for(int c: orig.keySet()) {\n            res.put(c, new HashSet<>(orig.get(c)));\n        }\n        return res;\n    }\n}\n```
['Backtracking', 'Recursion', 'Java']