DFS solution using recursion in Python
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen I first read this problem I tried using a greedy approach. I would first sort each
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen I first read this problem I tried using a greedy approach. I would first sort each row, then go through every row and try to pick the largest number possible. If it conflicted with another row I would try to resolve the conflict. It passed I think 533/543 test cases, all but the last 10.\n\nClearly the greedy approach of picking the largest number from each row was close, but not perfect.\n\nFor example, in the test case where grid = [[11, 8, 3], [17, 7, 3], [20, 13, 3], [20, 17, 3]] (after sorting), using greedy approach I was picking 11 from the first row, 17 from the second row, 20 from the third row. In the fourth row, the largest was 20 which is also what I picked from the 3rd row. So I cannot pick 20 twice. In the algorithm I had implemented, it would look at the next biggest numbers and decide what to do based on that.\n\nIn this case the next biggest no in row 3 is 13 and in row 4 is 17. Since I would like to keep 17 more than 13, I would decide to use 17 in row 4 and keep using 20 in row 3. (You can keep track of this with a diagram if it\'s getting confusing).\n\nBut now I have a conflict with row 2, since I am using 17 there as well. So again using the same approach, I would look at the next biggest numbers in both rows, 7 and 3. 7 is bigger so I would decide to use 7 in row 2 and 17 in row 4.\n\nThis gave me the solution 11, 7, 20, 17 (these are the numbers I picked from each row) giving a sum of 55. \n\nThis approach worked for almost all test cases, but not this one, because here the platform told me that we can actually achieve a larger sum of 61. I was perplexed and tried to figure out how to get 61.\n\nGoing row by row was not giving me 61 no matter how I tried. So I tried solving it by just trying to fit in the biggest numbers possible. I would take 20 from row 4, because I can take 17 from row 2 anyway. This would allow me to take 13 from row 3. Finally I pick 11 from row 1. This way I took the 4 biggest numbers in the entire grid: 20, 17, 13, 11. So this was guaranteed to be the best solution and it also gave a sum of 61.\n\nSo clearly whatever the best approach is, involves trying to fit the biggest number possible, regardless of which row it\'s from.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSo I decided to settle on an approach where I would find the largest number I can pick, for example in the above test case it would be 20. Now I can pick 20 from rows 3 or 4. I would explore both possibilities using dfs (you can imagine a tree where the root node has 2 children, 1 representing that I picked 20 from row 3 and the other representing that I picked 20 from row 4).\n\n![image.png](https://assets.leetcode.com/users/images/7c8cf2c1-70d9-4a02-bdf4-3ba49bdfdfe2_1725202107.5898361.png)\n\nI would keep track of the largest sum I have got so far. This way I will always get the optimal answer with decent time complexity as well.\n\nThis approach is guaranteed to give the optimal answer. For example the optimal answer is guaranteed to have 20, because if you have any other solution without 20, like you picked [11, 7, 13, 17] you can always get a better solution by replacing one of the numbers with 20 (wherever it is possible). For example here instead of picking 13 we can pick 20 to get [11, 7, 20, 17] or instead of 17 we can pick 20 to get [11, 7, 13, 20]. Both of these are guaranteed to better than the original solution of [11, 7, 13, 17] since 20 is the largest possible number you can include.\n\nLike this, at any step where you have used some rows, it is always best to pick the next largest number from the remaining rows. Because any other solution which doesn\'t involve that largest number will guaranteed be worse, as you can replace one of the smaller numbers with this largest number.\n\nThe way I implemented this in code is by using a recursive approach to implement DFS (Depth First Search). I always keep track of which rows I have picked so far. That has enough information to tell me which elements I have picked so far, since I\'m always picking the largest possible from each row.\n\nFor example if my array picked_rows_in_order = [2, 1, 0] that means I picked row 2 first (I am using 0-indexing now) which has 20 as it\'s largest element, so I picked 20 from that obviously. Then I picked row 1 (and element 17 from that) and then I picked row 0 (and element 11 from that row). I only have row 3 left, from which the max_element I can pick is 3. This would give me a sum of 51. \n\nUsing dfs I explore all the nodes of this tree. Note that this tree isn\'t too large, as it has only the optimum possibilities.\n\n# Complexity\n- Time complexity: n^d \nwhere \n1. d is the depth of the tree (= no of rows in the grid = no of individual elements we can select) \n2. n is the no of branches of the tree (approx. = no. of times a single element is repeated)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: n\\*m\\*d\nwhere\n1. n is the no of rows in the grid\n2. m is the no of cols in the grid\n3. d is the depth of the tree\nbecause we are using d levels of recursion and in each level, the largest thing we are storing is the grid of size n\\*m.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\ndef solve(grid, picked_rows_in_order, picked_rows, picked_elements, ans, cur_ans):\n    max_element=-1          #max element we can pick from remaining rows\n    max_element_rows=[]     #rows in which that max element is found\n    for i in range(len(grid)):\n        if i in picked_rows:\n            continue\n        for j in grid[i]:\n            if j in picked_elements:\n                continue\n            if j > max_element:\n                max_element = j\n                max_element_rows = [i]\n            elif j == max_element:\n                max_element_rows.append(i)\n            break\n    if max_element != -1:\n        for row in max_element_rows:\n            picked_rows_in_order.append(row)\n            picked_rows.add(row)\n            picked_elements.add(max_element)\n            ans = solve(grid, picked_rows_in_order, picked_rows, picked_elements, ans, cur_ans + max_element)\n            picked_rows_in_order.pop()\n            picked_rows.remove(row)\n            picked_elements.remove(max_element)\n        return max(ans, cur_ans)\n    else:\n        return max(ans, cur_ans)\n\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        #sorting elements in each row\n        for i in range(len(grid)):\n            grid[i].sort(reverse=True)\n        #using dfs to explore all possibilities while picking the largest number possible\n        picked_rows_in_order=[]     #contains indexes of rows in order they were picked (each time we choose the largest possible from each row)\n        picked_rows=set()           #contains indexes of rows picked so far, in a set for easy searching\n        picked_elements=set()       #contains elements picked so far\n        ans=0\n        cur_ans=0\n        ans = solve(grid, picked_rows_in_order, picked_rows, picked_elements, ans, cur_ans)\n        return ans\n```
['Depth-First Search', 'Recursion', 'Python3']