[LeetCode] 46. Permutations

Table of Contents

Description

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

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

Approach

To solve this problem, we build permutations by iteratively inserting each number into every possible position of existing permutations.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let permutations = [[]]; // Start with an empty permutation

  for (const num of nums) {
    const newPermutations = [];
    for (const permutation of permutations) {
      for (let i = 0; i <= permutation.length; i++) {
        // Insert num at every possible position
        newPermutations.push([
          ...permutation.slice(0, i),
          num,
          ...permutation.slice(i),
        ]);
      }
    }
    permutations = newPermutations;
  }

  return permutations;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n \times n!)$, where $n$ is the length of nums. For each of the $n!$ permutations, we insert each number into every possible position, and copying arrays of length up to $n$.

Space Complexity

The space complexity is $O(n \times n!)$ for storing all the permutations in the output. The extra space used during computation is $O(n \times n!)$ as well, since we generate all intermediate permutations.