Start learning free

LESSON 357 OF 540 · BACKTRACKING

Permutations in Scala: Backtracking in 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

    SCALA · BACKTRACKING

    Permutations in Scala, explained

    Problem overview

    The method permute receives an Array[Int] of distinct integers, nums, and returns a List[List[Int]] with every permutation: every way to put all the numbers in a row, each exactly once.

    The order of the result is fixed. Positions are filled from first to last, 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 permutations with the same first number, the second number decides the same way. So nums itself comes first and nums reversed comes last.

    For nums = [1, 2, 3] the answer is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. For nums = [3, 1, 2] it is [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]]: the numbers are tried as they stand in nums, 3 then 1 then 2, not in ascending order.

    Approach: fill one position at a time

    There are n! permutations, so any solution takes at least that long. The job is to generate each one once, in the right order, without building the wrong ones.

    Backtracking builds a permutation position by position in a list current. A boolean array used 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 append it), fill the remaining positions with a recursive call, then give it back (remove it and unmark it) so the next number can take its place. When current holds all n numbers, save a copy.

    Because the loop always starts at index 0 and tries the numbers in their order in nums, the result comes out in exactly the order the statement asks for.

    Step by step

    1. Create result as an empty ArrayBuffer[List[Int]](). It collects the permutations as they are found.
    2. Create used with Array.fill(nums.length)(false): one false per number. used(i) says whether nums(i) is already in the permutation being built.
    3. Start the search with backtrack(nums, used, ArrayBuffer[Int](), result): no position is filled and every number is free.
    4. Return result.toList, the last expression of the method.
    5. Write the helper backtrack, taking nums, used, current and result, and returning Unit.
    6. Check the base case: current.length == nums.length means every number is in it.
    7. Save a snapshot with result += current.toList and return.
    8. Loop over the candidates: for (i <- 0 until nums.length), always from 0, which gives the required order.
    9. Skip used numbers by wrapping the rest of the loop body in if (!used(i)). Scala has no continue, so the work goes inside the if.
    10. Mark the number with used(i) = true, so deeper calls won't take it again.
    11. Append it to current with +=.
    12. Recurse to fill the remaining positions.
    13. Give the number back with current.remove(current.length - 1).
    14. Unmark it with used(i) = false, so permutations built later can use it in another position.

    The solution in Scala

    In a file of your own, the code needs import scala.collection.mutable.ArrayBuffer at the top.

    class Solution {
    def permute(nums: Array[Int]): List[List[Int]] = {
        val result = ArrayBuffer[List[Int]]()
        val used = Array.fill(nums.length)(false)
        backtrack(nums, used, ArrayBuffer[Int](), result)
        result.toList
    }

    def backtrack(nums: Array[Int], used: Array[Boolean], current: ArrayBuffer[Int], result: ArrayBuffer[List[Int]]): Unit = {
        if (current.length == nums.length) {
            result += current.toList
            return
        }
        for (i <- 0 until nums.length) {
            if (!used(i)) {
                used(i) = true
                current += nums(i)
                backtrack(nums, used, current, result)
                current.remove(current.length - 1)
                used(i) = false
            }
        }
    }
}

    The Scala details worth a closer look:

    • val doesn't freeze the array. val used = Array.fill(...) fixes which array used refers to, but its elements can still change: used(i) = true is fine. The same goes for the ArrayBuffer.
    • Array.fill(n)(x) makes an array of n elements, each x. Two parameter lists: the count first, then the value. Array.fill(3)(false) is three false values.
    • Parentheses for arrays. Reading and writing an element are both written with parentheses: used(i) and used(i) = true.
    • The snapshot. current is one shared mutable buffer. Storing it directly would save a reference that ends up empty; current.toList makes an independent immutable list.
    • remove takes an index, so current.remove(current.length - 1) drops the last element.
    • 0 until n excludes n, so i is always a valid index. 0 to n would include it and run past the end.
    • Two undos. Both the buffer and the marker must be restored. Forgetting used(i) = false leaves the number blocked, and later permutations would come out short.

    Complexity

    Time: O(n · n!). There are n! permutations and copying each takes n steps. The recursion makes fewer than e · n! calls in total, and each call loops over the n numbers, which stays within the same bound.

    Space: O(n) extra, not counting the answer: current, used and one call per position.

    Edge cases and common mistakes

    • One number. [1] gives [[1]]: the base case fires on the first call.
    • Not sorted. The order depends on the order of nums, not on the values: [3, 1, 2] starts with [3, 1, 2]. Sorting the input first would change the answer.
    • Negative numbers. [-10, 0, 10] works the same way, since values are never used as indices; the loop works with positions.
    • Forgetting the unmark or the removal. If either undo is missing, the search runs out of free numbers early and the later permutations are missing or wrong.
    • Counting. Four numbers give 24 permutations, and eight, the biggest input, give 40,320.

    Testing

    • nums = [1, 2, 3] gives List(List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), List(2, 3, 1), List(3, 1, 2), List(3, 2, 1)).
    • nums = [3, 1, 2] gives List(List(3, 1, 2), List(3, 2, 1), List(1, 3, 2), List(1, 2, 3), List(2, 3, 1), List(2, 1, 3)).
    • nums = [1] gives List(List(1)).
    • nums = [-10, 0, 10] gives List(List(-10, 0, 10), List(-10, 10, 0), List(0, -10, 10), List(0, 10, -10), List(10, -10, 0), List(10, 0, -10)).
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free