Start learning free

LESSON 417 OF 675 · BACKTRACKING

Permutations

Practice O(n · n!)

You get an array nums of distinct integers. Return all of its permutations.

A permutation lines up all the numbers in some order. Each number is used exactly once.

The order of the permutations matters. First come all permutations that start with nums[0], then those that start with nums[1], and so on. Among those with the same first number, the second number follows the same rule. It goes through the numbers left, in their order in nums. Then the same goes for the third number, and so on.

So nums itself comes first. The reverse of nums comes last.

 

Example 1:

Input: nums = [7,2,5]
Output: [[7,2,5],[7,5,2],[2,7,5],[2,5,7],[5,7,2],[5,2,7]]
Explanation: The permutations start with 7, then 2, then 5.
That is the order of nums.
Of the two that start with 2, the one with 7 next comes first.
That is because 7 comes before 5 in nums.

Example 2:

Input: nums = [-3,8]
Output: [[-3,8],[8,-3]]
Explanation: Two numbers can be lined up in two ways: as given, then swapped.

Example 3:

Input: nums = [6]
Output: [[6]]
Explanation: A single number can be lined up in only one way.

 

Constraints:

  • nums holds 1 to 8 numbers.
  • Each number is between -10 and 10.
  • No number appears twice.

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