Permutation Sequence
HardPrompt
The set [1, 2, 3, ..., n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Example 1:
Input: n = 3, k = 3
Output: "213"Example 2:
Input: n = 4, k = 9
Output: "2314"Example 3:
Input: n = 3, k = 1
Output: "123"
Constraints:
1 <= n <= 91 <= k <= n!
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating all possible permutations of the numbers from 1 to n. We can use a recursive backtracking algorithm to find every permutation. As we generate them, we store them in a list. Since the standard backtracking approach of picking the smallest available number first generates permutations in lexicographical order, the k-th permutation will be the element at index k-1 in our list.
Algorithm
- Create a list to store the resulting permutations.
- Implement a recursive helper function, say
backtrack(current_permutation, remaining_numbers). - The base case for the recursion is when
remaining_numbersis empty. At this point, a full permutation has been formed, so we add it to our list of permutations. - In the recursive step, iterate through the
remaining_numbers. For each number, add it to thecurrent_permutation, remove it fromremaining_numbers, and make a recursive call. - After the recursive call returns, backtrack by removing the number from
current_permutationand adding it back toremaining_numbersto explore other possibilities. - The initial call will be with an empty permutation and a list of numbers from 1 to
n. - After the recursion completes, the list will contain all
n!permutations in order. Return the string at indexk-1.
Walkthrough
class Solution { public String getPermutation(int n, int k) { List<String> permutations = new ArrayList<>(); boolean[] used = new boolean[n + 1]; generatePermutations(new StringBuilder(), n, permutations, used); return permutations.get(k - 1); } private void generatePermutations(StringBuilder current, int n, List<String> result, boolean[] used) { if (current.length() == n) { result.add(current.toString()); return; } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; current.append(i); generatePermutations(current, n, result, used); // Backtrack current.deleteCharAt(current.length() - 1); used[i] = false; } } }}Complexity
Time
O(n * n!)
Space
O(n * n!)
Trade-offs
Pros
Simple to understand if you are familiar with backtracking.
Cons
Extremely inefficient for larger
n(even forn=9,9!is large).It will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on most platforms.
Solutions
Solution
public class Solution { public string GetPermutation ( int n , int k ) { var ans = new StringBuilder (); int vis = 0 ; for ( int i = 0 ; i < n ; ++ i ) { int fact = 1 ; for ( int j = 1 ; j < n - i ; ++ j ) { fact *= j ; } for ( int j = 1 ; j <= n ; ++ j ) { if ((( vis >> j ) & 1 ) == 0 ) { if ( k > fact ) { k -= fact ; } else { ans . Append ( j ); vis |= 1 << j ; break ; } } } } return ans . ToString (); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.