Start learning free

LESSON 357 OF 540 · BACKTRACKING

Permutations in TypeScript: Backtracking with a used Array

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

    TYPESCRIPT · BACKTRACKING

    Permutations in TypeScript, explained

    Problem overview

    The method permute(nums) receives an array of distinct integers and returns every permutation of it: every way to put all of its numbers in a row, each number exactly once.

    The order of the permutations is fixed. Fill the positions from first to last, always trying the numbers in their order in nums. All the permutations that start with nums[0] come first, then those that start with nums[1], and so on; among permutations with the same first number, the second number decides in the same way. For [1, 2, 3] the answer 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], then [3, 2, 1], then the permutations that start with 1, and ends with [2, 1, 3]. With one number, [1] gives [[1]].

    Approach: fill one position at a time

    An array of n distinct numbers has n! permutations (6 for three numbers, 40,320 for eight), so the output itself is large and the task is to generate each permutation exactly once.

    Backtracking builds a permutation one position at a time in a list current. For the next position, go through the numbers of nums in order and take each one that isn't already in current. Taking a number means marking it as used and appending it; a recursive call then fills the remaining positions. Afterwards the number is given back (removed and unmarked) so that the next number can take its place. When current holds all n numbers, a copy of it is saved.

    The array used has one true/false value per number, and used[i] says whether nums[i] is already in current. It's how the search avoids using a number twice.

    Because every loop goes through the numbers from index 0 upwards, the permutations come out in exactly the order described above.

    Step by step

    1. Create result, a number[][] that starts empty and will collect the permutations.
    2. Create used, one false per number: new Array(nums.length).fill(false). new Array(n) makes n empty slots and fill(false) sets each of them.
    3. Start the search with this.backtrack(nums, used, [], result): no position is filled yet and every number is free.
    4. Return result. The helper filled this same array.
    5. Declare the helper backtrack(nums, used, current, result), returning void. Each call fills one more position of current and calls itself for the rest.
    6. Check whether current is full: current.length === nums.length means it holds every number once.
    7. Save a snapshot with [...current], then return. current keeps changing, so result needs its own copy.
    8. Loop over every index i from 0 to nums.length - 1. Starting at 0 every time and going in order is what gives the order the answer needs.
    9. Skip used numbers with continue. A number already in current can't appear twice.
    10. Mark nums[i] as used, so that deeper calls won't take it again.
    11. Push it onto current: it fills the next position.
    12. Recurse to fill the remaining positions. Nothing else needs passing, since used and current already say what is taken.
    13. Pop it from current to give the position back.
    14. Unmark it, used[i] = false, so permutations built later can use it somewhere else.

    The solution in TypeScript

    class Solution {
    permute(nums: number[]): number[][] {
        const result: number[][] = [];
        const used: boolean[] = new Array(nums.length).fill(false);
        this.backtrack(nums, used, [], result);
        return result;
    }
    backtrack(nums: number[], used: boolean[], current: number[], result: number[][]): void {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            current.push(nums[i]);
            this.backtrack(nums, used, current, result);
            current.pop();
            used[i] = false;
        }
    }
}

    TypeScript details worth knowing

    The copy matters. current is a single array shared by all the calls. Pushing it directly would store the same reference many times, and by the end of the search it is empty again, so every entry of result would show the same empty array. [...current] creates a new array holding the current numbers.

    new Array(n).fill(false). new Array(3) alone is three empty slots, printed as [ <3 empty items> ], and fill(false) turns them into [false, false, false]. With fill and a number or boolean this is fine. With an object such as [], fill would put the same object in every slot: new Array(2).fill([]), followed by a push into the first element, shows [[1],[1]].

    continue skips the rest of the current turn of the loop and moves on to the next i.

    The types are checked by the compiler and erased when it produces JavaScript, so boolean[] and void don't exist at run time.

    Complexity

    Time: O(n · n!). There are n! permutations, and copying each one takes n steps. The calls that build them, fewer than e · n! in all, each loop over the n numbers, which gives the same O(n · n!) bound.

    Space: O(n) besides the answer. The search holds current, used and one call per position, each of size at most n. The answer itself, with n! permutations, is not counted.

    Edge cases and common mistakes

    • One number. [1] gives [[1]]. Two numbers, [1, 2], give [[1,2],[2,1]].
    • Forgetting to unmark. If used[i] stays true after the recursive call, later branches think the number is still taken and the result comes out short.
    • Forgetting pop(). current grows past n numbers and the "full" check never matches again.
    • Not copying current. Every saved entry ends up pointing to the same array.
    • Looping from the wrong place. Starting the loop after the index just taken would miss permutations such as [2, 1, 3]. Every position must try all the numbers from index 0, skipping the used ones.
    • Sorting nums first. The order of the output follows nums as given. For [3, 1, 2] the first permutation is [3, 1, 2], not [1, 2, 3].

    Testing

    The lesson's code gives these results:

    permute([1, 2, 3]) -> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
permute([3, 1, 2]) -> [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]]
permute([1])       -> [[1]]
permute([1, 2])    -> [[1,2],[2,1]]

    For the numbers 1 to 8 it returns 40,320 permutations.

    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free