Permutations

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

Permutations

Difficulty: Medium

Problem Statement

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

Examples

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]]

Example 2

Input: nums = [0, 1]

Output: [[0,1], [1,0]]

Example 3

Input: nums = [1]

Output: [[1]]

Constraints

• 1 ≤ nums.length ≤ 6
• −10 ≤ nums[i] ≤ 10
• All the integers in nums are unique.

Solution

This uses the same "swap and recurse" technique as generating permutations of a string, but works directly on the array of numbers.

Steps

• We go through the array one position at a time, starting from the beginning (start).
• At each position, we try placing every remaining number there, one at a time, by swapping it into place with the current position.
• After placing a number at the current position, we move on to the next position and repeat, using recursion.
• Once we reach the last position (start === nums.length - 1), the array is fully arranged into one complete permutation. We save a copy of it into our results.
• As each recursive call finishes, we swap back the numbers we swapped earlier. This resets the array so the next option at this position can be tried cleanly.

Code

function generatePermute(nums, start, result) {

    if (start === nums.length - 1) {
        result.push([...nums]);
        return;
    }

    for (let i = start; i < nums.length; i++) {

        [nums[start], nums[i]] = [nums[i], nums[start]];

        generatePermute(nums, start + 1, result);

        [nums[start], nums[i]] = [nums[i], nums[start]];
    }
}

var permute = function(nums) {

    var result = [];

    generatePermute(nums, 0, result);

    return result;
};