60. Permutation Sequence

How to solve Permutation Sequence (LeetCode 60): the approach in brief

The problem

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

Pattern

Permutation Sequence is a Backtracking Patterns problem, in the Permutations subpattern. The pattern covers subsets, permutations, combinations, N-Queens, and word search

Generate all permutations using backtracking. Handle duplicates and next permutation.

Approach outline

1. Consider how permutations can be generated using backtracking, and think about the structure of the solution space as a tree of choices.
2. Instead of generating all permutations, explore how the order of permutations relates to factorial numbers and how this can guide your selection at each step.
3. Try to determine which number should be placed in each position by calculating how many permutations start with a particular digit, using factorials to skip over groups of permutations.

Complexity

The reference solution runs in O(n^2) time and O(n) space.

Asked at

Permutation Sequence has been reported in interviews at Amazon, Adobe.