Kotlin | 100% (no competition) | explained
This is an interesting problem because it looks easy!  My initial solution didn\'t take the rows into account, and so got the wrong answer.  I then used a prior
This is an interesting problem because it looks easy!  My initial solution didn\'t take the rows into account, and so got the wrong answer.  I then used a priority queue, but that did not work with the recursion.  So here I will describe my final solution.  It could probably be made more efficient if memorization is added (I don\'t agree that it should be called memoization - why make up a new word?).\n\nOne could call this a greedy algorithm, where it tries the largest numbers first, but you have to also try without the largest numbers because of the issue with the rows.  I decided to use an array and then sort it.  Arrays are efficient when it comes to accessing items.  Into the array, I put the value from the grid and the row that it is on.  The column of the item doesn\'t matter.  I also decided to use an IntArray for each item in the array, although a pair could have been used.\n\nOnce all the items have been added to the array, I sort it in descending order by the value ([0]).  Recursion is nice because you can do each step, one at a time.  Here, I start with the highest value, which is in position 0 in the nums array.  Each call to next will process all of the same values.  Since we cannot use any row more than once, a boolean array is used to mark that row as used.  Following the call, it is returned to false since another item from that row may be selected.\n\nFunction next looks through nums for all values that are the same, and passes the index of the following numbers to the next call of next.  Since no duplicate numbers can be used, only one of them is tried at a time.\n\nRecursion ends when either we have selected all the numbers we can (count = 0) or there are no more numbers to choose from.  This can happen if there are many duplicate numbers, for example.\n\nLastly, it\'s worth mentioning the two global variables.  nums is global since it doesn\'t change once it\'s set up, and max, since that can be set at the end of each recursion, and easily returned.\n\nHere is my solution:\n\n```\nclass Solution {\n    \n    var nums = Array<IntArray>(0) { IntArray(0) }\n    var max = 0\n    \n    fun maxScore(grid: List<List<Int>>): Int {\n        var numsNdx = 0\n        nums = Array<IntArray>(grid.size * grid[0].size) { IntArray(2) }\n        for (row in 0..grid.lastIndex) {\n            for (col in 0..grid.get(row).lastIndex) {\n                nums[numsNdx++] = intArrayOf(grid.get(row).get(col), row)                \n            }\n        }\n        nums.sortByDescending { it[0] }\n        var rowUsed = BooleanArray(grid.size)\n        next(grid.size, 0, 0, rowUsed)\n        return max\n    }\n    \n    fun next(count: Int, sum: Int, numsNdx: Int, rowUsed: BooleanArray) {\n        if (count == 0 || numsNdx == nums.size) {\n            if (sum > max) {\n                max = sum\n            }\n            return\n        }\n        \n        var startNdx = numsNdx\n        var endNdx = numsNdx\n        var last = nums[numsNdx][0]\n        var found = false\n        var cand : IntArray\n        while (endNdx <= nums.lastIndex && nums[endNdx][0] == last) {\n            endNdx++\n        }\n        for (ndx in startNdx..endNdx - 1) {\n            cand = nums[ndx]\n            if (!rowUsed[cand[1]]) {\n                found = true\n                rowUsed[cand[1]] = true\n                next(count - 1, sum + last, endNdx, rowUsed)\n                rowUsed[cand[1]] = false\n            }\n            if (count == 1 && found) {\n                break\n            }\n        }\n        if (!found) {\n            next(count, sum, endNdx, rowUsed)\n        }\n    }\n}\n```\n\nThanks for reading.  Please upvote if you like the solution and/or the explanation.\n
['Array', 'Backtracking', 'Recursion', 'Sorting', 'Kotlin']