Start learning free

LESSON 357 OF 540 · BACKTRACKING

Permutations in Kotlin: Backtracking with a used Array, O(n · n!)

Practice O(n · n!) Read the full explanation

Given an array nums of distinct integers, return every permutation of nums: every way to put all of its numbers in a row, each number exactly once.

Return the permutations in the order you get by filling the positions from first to last and always trying the numbers in their order in nums: every permutation that starts with nums[0] comes first, then every one that starts with nums[1], and so on. Among the permutations with the same first number, the second number decides the same way, trying the numbers that are left in their order in nums; then the third, and so on. So nums itself always comes first, and nums reversed comes last.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Explanation: Two permutations start with 1, then two with 2, then two with 3.
After 1, the numbers left are 2 and 3, tried in that order, so [1,2,3] comes before [1,3,2].

Example 2:

Input: nums = [3,1,2]
Output: [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]]
Explanation: The numbers are tried in their order in nums, 3 then 1 then 2, not in ascending order.
After 1, the numbers left are 3 and 2, in that order in nums, so [1,3,2] comes before [1,2,3].

Example 3:

Input: nums = [1]
Output: [[1]]
Explanation: One number can be put in a row in only one way.

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Build a permutation one position at a time in a list current, and keep an array used of true/false values, one per number, that says which numbers current already holds. For the next position, go through the numbers in order and skip the used ones; for each unused number, take it (mark it used and add it to current), fill the remaining positions with a recursive call, then give it back (remove it and mark it unused) so the next number can take its place. When current holds all n numbers, save a copy of it. Trying the numbers in their order in nums gives exactly the order above.

There are n! permutations. Copying each one takes n steps, and the calls that build them, fewer than e · n! in all, each loop over the n numbers, so the time is O(n · n!). Besides the answer, the extra space is O(n): current, used and one call per position.

STEP 1 OF 14
    Ctrl + Enter to check

    KOTLIN · BACKTRACKING

    Permutations in Kotlin, explained

    Problem overview

    The function permute(nums: IntArray): List<List<Int>> receives an array of distinct integers and returns every permutation: every way to put all the numbers in a row, each exactly once.

    The order of the answer is fixed. Positions are filled from first to last, and the numbers still available are always tried in their order in nums. All permutations starting with nums[0] come first, then those starting with nums[1], and so on, with the same rule applied to the second position, the third, and so on. For nums = [1, 2, 3] the result is:

    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

    The order follows nums, not ascending values. For [3, 1, 2] the answer starts with [3, 1, 2] and ends with [2, 1, 3]:

    [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]]

    Approach: fill one position at a time

    There are n! permutations, so the answer is large and any solution must build all of them. The question is how to build each exactly once and in the right order.

    Backtracking builds one permutation position by position. It keeps a list current with the numbers placed so far and a BooleanArray named used, where used[i] says whether nums[i] is already in current. To fill the next position, it loops over the indexes from 0, skips used numbers, and for each free number does three things:

    1. Take it: mark it used and add it to current.
    2. Recurse to fill the remaining positions.
    3. Give it back: remove it from current and mark it unused, so the next number in the loop can take this position.

    When current holds nums.size numbers, it is a complete permutation, and a copy goes into the result. Because the loop always goes through indexes in increasing order, the output order is exactly the one described above.

    The trace for [1, 2, 3] shows the shape. Each level of indentation fills one more position:

    take 1 -> [1]
  take 2 -> [1, 2]
    take 3 -> [1, 2, 3]
      save [1, 2, 3]
  take 3 -> [1, 3]
    take 2 -> [1, 3, 2]
      save [1, 3, 2]
take 2 -> [2]
  take 1 -> [2, 1]
    take 3 -> [2, 1, 3]
      save [2, 1, 3]
  take 3 -> [2, 3]
    take 1 -> [2, 3, 1]
      save [2, 3, 1]
take 3 -> [3]
  take 1 -> [3, 1]
    take 2 -> [3, 1, 2]
      save [3, 1, 2]
  take 2 -> [3, 2]
    take 1 -> [3, 2, 1]
      save [3, 2, 1]

    Step by step

    1. Create result as an empty mutableListOf<List<Int>>(). Each permutation is a list, so the result holds lists.
    2. Create used as BooleanArray(nums.size). Every element starts as false, and the elements can change even though used is a val.
    3. Start the search with nums, used, an empty mutableListOf() and result. Nothing is placed yet and every number is free.
    4. Return result, which the helper has filled.
    5. Write the helper's signature, taking the array, used, current and result.
    6. Check whether current is full: current.size == nums.size means it holds every number once.
    7. Save a copy and return. current.toList() makes a snapshot, since current keeps changing.
    8. Loop over 0 until nums.size. Starting at 0 and going up gives the required order.
    9. Skip used numbers with continue. A permutation can't repeat a number.
    10. Mark the number by setting used[i] to true, so deeper calls won't take it.
    11. Add nums[i] to the end of current.
    12. Recurse to fill the remaining positions.
    13. Remove the last number of current with removeAt(current.size - 1).
    14. Unmark it: set used[i] back to false, so later permutations can place it elsewhere.

    The solution in Kotlin

    class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val used = BooleanArray(nums.size)
        backtrack(nums, used, mutableListOf(), result)
        return result
    }

    fun backtrack(nums: IntArray, used: BooleanArray, current: MutableList<Int>, result: MutableList<List<Int>>) {
        if (current.size == nums.size) {
            result.add(current.toList())
            return
        }
        for (i in 0 until nums.size) {
            if (used[i]) {
                continue
            }
            used[i] = true
            current.add(nums[i])
            backtrack(nums, used, current, result)
            current.removeAt(current.size - 1)
            used[i] = false
        }
    }
}

    Kotlin details worth a look:

    • BooleanArray. It is the primitive array of Boolean, created as BooleanArray(n) with every element false. Arrays are mutable, so used[i] = true works even though used is a val: val fixes which array the name refers to, not its contents.
    • Shared mutable state. used and current are passed by reference, so every recursive call sees and changes the same two objects. That is why each call must undo exactly what it did.
    • Copying with toList(). result.add(current) would store the shared list itself. After the search it is empty again, so every saved entry would show the same empty list. toList() creates a new list with the same numbers.
    • 0 until nums.size. The range excludes its end, so i is always a valid index. for (i in nums.indices) means the same.
    • continue in a for loop. It skips the rest of this turn and goes on with the next i.
    • Read-only and mutable lists. The helper takes MutableLists because it adds and removes. Returning result as List<List<Int>> needs no conversion.

    Complexity

    Time: O(n · n!). There are n! permutations, and each needs a copy of n numbers. The loops in the recursion cost about n checks per call, and the number of calls is within a small constant factor of n!, so the total stays O(n · n!).

    Space: O(n) extra, not counting the answer. The arrays current and used hold at most n items, and the recursion is at most n + 1 calls deep. The answer itself holds n! lists of n numbers.

    Edge cases and common mistakes

    • One number. [1] gives [[1]]: there is one way to put a single number in a row.
    • Negative numbers. [-10, 10] gives [[-10, 10], [10, -10]]. The search works with indexes, so the values don't matter.
    • Forgetting to unmark. If used[i] = false is missing, a number stays marked after its first use, and the search can't use it again in other branches. For [1, 2, 3] the result is just [[1, 2, 3]].
    • Forgetting to remove from current. The list keeps growing, and its size never matches nums.size at the right moments.
    • Saving current without copying. Every saved entry ends up as the same empty list.
    • Sorting the input first. The required order follows the numbers' order in nums. For [3, 1, 2] the first permutation is [3, 1, 2], not [1, 2, 3].
    • Size. Eight numbers give 40320 permutations, and each extra number multiplies the count by the new length.

    Testing

    • nums = [1, 2, 3] gives [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
    • nums = [3, 1, 2] gives [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]].
    • nums = [1] gives [[1]].
    • nums = [-10, 10] gives [[-10, 10], [10, -10]].
    • The numbers 1 to 8 give a list of 40320 permutations.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free