Advanced Recursion Techniques

Lesson Overview

Quick Example

To give you a small taste of what is in store, let's take a look at a recursive function that generates all permutations of a list of numbers. The strategy here is to use a method known as backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to computational problems by incrementally building candidates and abandoning a candidate as soon as it determines that the candidate cannot possibly be completed as a valid solution.

In our example, we use a MutableList to store the numbers so that we can modify them in place. At each recursion level, we choose which number should go at position first by swapping nums[first] with each element from first to the end. We then move one level deeper into the recursion to fix the next position and finally swap the elements back to reset the state for the next iteration. Once we reach the end of the list, we create a copy of the current state of the list and add it to our results.

Kotlin
fun permute(nums: MutableList<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()

    // Define a local function for backtracking
    fun backtrack(first: Int) {
        // If we've reached the end of the list, we found a complete permutation
        if (first == nums.size) {
            result.add(nums.toList()) // Add a copy of the current list state
            return
        }

        for (i in first until nums.size) {
            // Swap numbers to explore a new permutation
            val temp = nums[first]
            nums[first] = nums[i]
            nums[i] = temp

            // Move one level deeper in the recursion, fixing the next position
            backtrack(first + 1)

            // Backtrack: Swap them back to reset the state for the next iteration
            val tempBack = nums[first]
            nums[first] = nums[i]
            nums[i] = tempBack
        }
    }

    backtrack(0)
    return result
}

fun main() {
    val numbers = mutableListOf(1, 2, 3)
    val permutations = permute(numbers)
    println(permutations) 
    // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
}
Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal