Marc Lester Tan

Here’s a medium (problem)[https://leetcode.com/problems/campus-bikes-ii/] which can be solved by using backtracking. Since the problem mentioned about minimizing the sum of distances for a possible combination of workers and bikes, we can use backtracking to go through all possible combinations of bikes and workers. We also keep track of the minimum sum and use that as the final answer.

class Solution {
    infix fun Pair<Int, Int>.distanceFrom(param: Pair<Int, Int>): Int = 
        (Math.abs(this.first - param.first) + Math.abs(this.second - param.second)).toInt()
    
    fun assignBikes(workers: Array<IntArray>, bikes: Array<IntArray>): Int {
        var min = Integer.MAX_VALUE
        // keeps track of bikes that has been used already
        val bikeStates = BooleanArray(bikes.size){ true }
        
        fun helper(workerIndex: Int, currentSum: Int){
            // base case
            if(workerIndex == workers.size){
                min = Math.min(min, currentSum)
                return
            }
            
            val worker = workers[workerIndex]            
            for(i in 0 until bikes.size){
                if(!bikeStates[i]) continue
                
                val bike = bikes[i]
                val sum = Pair(worker.first(), worker.last()) distanceFrom Pair(bike.first(), bike.last())
                bikeStates[i] = false
                helper(workerIndex + 1, currentSum + sum)
                bikeStates[i] = true
            }
        }
        
        helper(0, 0)        
        return min
    }
}

Runtime: 1372 ms, faster than 50.00% of Kotlin online submissions for Campus Bikes II.
Memory Usage: 36.5 MB, less than 100.00% of Kotlin online submissions for Campus Bikes II.