Start learning free

LESSON 353 OF 536 · BACKTRACKING

Permutations in JavaScript: 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

    JAVASCRIPT · BACKTRACKING

    Permutations in JavaScript, explained

    Problem overview

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

    The order of the result is fixed. Fill the positions from first to last, always trying the numbers in their order in nums. So every permutation that starts with nums[0] comes first, then every one that starts with nums[1], and so on, with the same rule applied to the second position, the third, and the rest.

    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]]: two permutations start with 1, two with 2 and two with 3. For nums = [3, 1, 2] the numbers are tried in the order 3, 1, 2, not in ascending order, so the result is [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]]. For [1] the result is [[1]].

    Approach: build one position at a time

    A permutation of n numbers has n positions. The first can hold any of the n numbers, the second any of the n - 1 that are left, and so on, so there are n! permutations. Any solution has to produce them all.

    Backtracking builds them with one recursive function. It keeps the permutation so far in current. To fill the next position, it goes through the numbers in order and skips those already in current. For each free number it does three things: take it, fill the remaining positions with a recursive call, and give it back so that the next number can take its place. When current holds all the numbers, it is a finished permutation and gets saved.

    To know which numbers are taken, the code keeps an array used of booleans, with used[i] telling whether nums[i] is in current. Looking up a flag by index is faster than searching current for the number each time.

    Trying the numbers in the order of nums at every position produces exactly the order the problem asks for. Here are the first events of the search for [1, 2, 3]:

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

    Step by step

    1. Create result as an empty array. It collects the permutations.
    2. Create used with new Array(nums.length).fill(false): one false per number. new Array(n) alone makes n empty slots, and fill(false) sets each one.
    3. Start the search with this.backtrack(nums, used, [], result). Nothing is placed yet, so the permutation so far is empty and every number is free.
    4. Return result. The helper added to this same array.
    5. Declare the helper backtrack(nums, used, current, result) inside the class. Each call fills one more position.
    6. Check whether current is full: current.length === nums.length. A full current holds every number once.
    7. Save a copy and return. [...current] copies the numbers into a new array. current keeps changing as the search goes on, so saving it directly would store something that changes later.
    8. Loop over every index i from 0 to nums.length - 1. Always starting at 0 and going up is what gives the required order.
    9. Skip taken numbers. If used[i] is true, continue moves to the next i.
    10. Mark the number: set used[i] to true, so deeper calls won't take it again.
    11. Push nums[i] onto current. This fills the next position.
    12. Recurse with the same four arguments. used and current already describe what is taken, so nothing else is passed.
    13. Give the number back with current.pop(), which removes the last number.
    14. Unmark it: set used[i] back to false, so later permutations can place it elsewhere.

    The solution in JavaScript

    class Solution {
    permute(nums) {
        const result = [];
        const used = new Array(nums.length).fill(false);
        this.backtrack(nums, used, [], result);
        return result;
    }
    backtrack(nums, used, current, result) {
        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;
        }
    }
}

    The JavaScript details worth a closer look:

    • Arrays are passed by reference. used, current and result are the same arrays in every call. That is what lets the recursion share one result, and it is also why every change to current and used must be undone before the call returns.
    • The copy matters. If the code pushed current itself, result would hold several references to one array, and by the end that array is empty again. For nums = [1, 2], a version that forgets the copy returns [[],[]] instead of [[1,2],[2,1]].
    • The spread [...current] builds a new array holding the same numbers. It makes a shallow copy, which is enough because the elements are numbers.
    • new Array(n).fill(false). Without fill, the array has empty slots that read as undefined, which is falsy, so it would even seem to work. Filling it makes the intent explicit and gives a real array of booleans.
    • continue in a for loop. It jumps to the increment i++ and then the next test, so skipping a taken number never skips the undo steps of another one.
    • === for the length check. Both sides are numbers, and === compares without converting types.

    Complexity

    Time: O(n · n!). There are n! permutations, and saving each one copies n numbers. The recursion builds them through fewer than e · n! calls in total, and each call loops over the n numbers, so the whole search stays within O(n · n!). With n up to 8 that is 40,320 permutations at most.

    Space: O(n) beyond the answer. The extra memory is current, used and the recursion, which is n calls deep. The answer itself holds n · n! numbers.

    Edge cases and common mistakes

    • One number. [1] returns [[1]]: the first call takes the only number, and current is full at once.
    • Two numbers. [1, 2] returns [[1,2],[2,1]].
    • Order follows nums. For [3, 1, 2] the first permutation is [3,1,2], the array itself. Sorting nums first would change the order of the result.
    • Forgetting the copy. The result then holds the same array several times, all empty at the end.
    • Forgetting to unmark. If used[i] stays true after the recursive call, later branches think the number is taken and the result comes out incomplete.
    • Forgetting pop(). current keeps numbers that should have been removed, so it no longer matches the marks in used and the saved permutations are wrong.
    • Starting the loop at i + 1. That is the pattern for subsets, where order doesn't matter. Permutations need every unused number at every position, so the loop starts at 0.

    Testing

    • [1, 2, 3] gives [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
    • [3, 1, 2] gives [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]].
    • [1] gives [[1]].
    • [1, 2] gives [[1,2],[2,1]].
    • [1, 2, 3, 4, 5, 6, 7, 8] returns 40,320 permutations.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free