Permutation Sequence
Hard · Backtracking · Math · Recursion
Problem
The numbers 1 through n can be arranged in n! different orders. Write each arrangement as a string of digits and sort the strings in increasing order.
Given n and k, return the k-th arrangement (1-indexed) in that sorted list.
Examples
Input: n = 3, k = 5 Output: "312"
The sorted list begins 123, 132, 213, 231, 312.
Input: n = 4, k = 10 Output: "2341"
Six arrangements start with 1; the fourth one starting with 2 is 2341.
Input: n = 4, k = 1 Output: "1234"
The first arrangement is always ascending order.
Constraints
- 1 <= n <= 9
- 1 <= k <= n!
Approaches
- Baseline: step through the arrangements in order — time O(k·n), space O(n)
Follow-up
The same counting answers the inverse question, the position of a given arrangement, and extends to letters that repeat by replacing (n - 1)! with a multinomial count. Both are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
