# Permutation Sequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/permutation-sequence)
Canonical: https://scaleengineer.com/dsa/problems/permutation-sequence
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [X](https://scaleengineer.com/companies/x), [Jump Trading](https://scaleengineer.com/companies/jump-trading)
---
## Problem
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`:

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"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 <= 9`
* `1 <= k <= n!`

# Approaches
## Brute-Force using Recursion
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.
**Time:** O(n * n!) · **Space:** O(n * n!)
**Pros:** Simple to understand if you are familiar with backtracking.
**Cons:** Extremely inefficient for larger `n` (even for `n=9`, `9!` is large).; It will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on most platforms.
### Explanation
```java
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;
            }
        }
    }
}
```
### 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_numbers` is 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 the `current_permutation`, remove it from `remaining_numbers`, and make a recursive call.
*   After the recursive call returns, backtrack by removing the number from `current_permutation` and adding it back to `remaining_numbers` to 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 index `k-1`.

## Iterative using Next Permutation
This method avoids generating all permutations at once. Instead, it starts with the first permutation (which is "123...n") and then iteratively finds the next lexicographical permutation `k-1` times.
**Time:** O(k * n) · **Space:** O(n)
**Pros:** More space-efficient than the full backtracking approach.; Faster if `k` is small.
**Cons:** Still too slow if `k` is large, leading to a "Time Limit Exceeded" error.
### Explanation
```java
class Solution {
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }

        for (int i = 1; i < k; i++) {
            nextPermutation(nums);
        }

        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    private void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}
```
### Algorithm
*   Create the first permutation by concatenating numbers from 1 to `n`.
*   Loop `k-1` times. In each iteration, find the next lexicographical permutation of the current one.
*   The algorithm to find the next permutation is as follows:
    a.  Find the largest index `i` such that `perm[i] < perm[i+1]`. If no such index exists, this is the last permutation.
    b.  Find the largest index `j > i` such that `perm[i] < perm[j]`.
    c.  Swap the elements at `i` and `j`.
    d.  Reverse the sub-array from index `i+1` to the end.
*   After the loop finishes, the current permutation is the `k`-th one.

## Mathematical Approach using Factorials
This is the most efficient approach. It mathematically constructs the `k`-th permutation directly without generating any other permutations. The idea is to determine each digit of the permutation one by one, from left to right. For `n` numbers, there are `n!` permutations. These can be divided into `n` blocks, where each block consists of `(n-1)!` permutations that start with the same number. By using `k` and the size of these blocks, we can determine which block the `k`-th permutation falls into, and thus determine the first digit of our result. We then update `k` to be the index within that block and repeat the process for the remaining numbers.
**Time:** O(n^2) · **Space:** O(n)
**Pros:** Very efficient and guaranteed to pass within the time limits for the given constraints.; Directly calculates the result without unnecessary computations.
**Cons:** The logic is less intuitive than brute-force and requires understanding the mathematical properties of permutations.
### Explanation
```java
class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n + 1];
        StringBuilder sb = new StringBuilder();

        // Create a list of numbers to get indices
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        // Pre-compute factorials
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            // Note: n! can be large, but for n<=9, it fits in an int
            factorial[i] = factorial[i - 1] * i;
        }

        // Adjust k to be 0-indexed
        k--;

        for (int i = n; i >= 1; i--) {
            int blockSize = factorial[i - 1];
            int index = k / blockSize;
            sb.append(numbers.get(index));
            numbers.remove(index);
            k = k % blockSize;
        }

        return sb.toString();
    }
}
```
### Algorithm
*   Create a list of available numbers, `[1, 2, ..., n]`.
*   Pre-compute factorials up to `(n-1)!`.
*   Adjust `k` to be 0-indexed by subtracting 1 (`k--`). This simplifies index calculations.
*   Iterate from `n` down to 1. In each step `i`:
    a.  Calculate the size of the permutation blocks for the remaining `i-1` numbers: `blockSize = (i-1)!`.
    b.  The index of the number to pick from the current list of available numbers is `index = k / blockSize`.
    c.  Append the number at `index` to the result.
    d.  Remove that number from the list of available numbers.
    e.  Update `k` for the next iteration: `k = k % blockSize`.
*   Return the constructed permutation string.

# Solutions
### CSharp

```csharp
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 (); } }
```

### Java

```java
class Solution { public String getPermutation ( int n , int k ) { StringBuilder ans = new StringBuilder (); boolean [] vis = new boolean [ n + 1 ]; 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 ]) { if ( k > fact ) { k -= fact ; } else { ans . append ( j ); vis [ j ] = true ; break ; } } } } return ans . toString (); } }
```

### CPP

```cpp
class Solution { public: string getPermutation ( int n , int k ) { string ans ; bitset < 10 > vis ; 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 ]) continue ; if ( k > fact ) k -= fact ; else { ans += to_string ( j ); vis [ j ] = 1 ; break ; } } } return ans ; } };
```

### Python

```python
class Solution : def getPermutation ( self , n : int , k : int ) -> str : nums = list ( range ( 1 , n + 1 )) factorial = [ 1 ] * ( n + 1 ) for i in range ( 1 , n + 1 ): factorial [ i ] = factorial [ i - 1 ] * i result = [] k -= 1 for i in range ( n , 0 , - 1 ): digit = k // factorial [ i - 1 ] result . append ( str ( nums [ digit ])) nums . pop ( digit ) k %= factorial [ i - 1 ] return '' . join ( result ) ########## class Solution : def getPermutation ( self , n : int , k : int ) -> str : ans = [] vis = [ False ] * ( n + 1 ) for i in range ( n ): fact = 1 for j in range ( 1 , n - i ): fact *= j for j in range ( 1 , n + 1 ): if not vis [ j ]: if k > fact : k -= fact else : ans . append ( str ( j )) vis [ j ] = True break return '' . join ( ans )
```