Algorithm

Problem Name: 60. Permutation Sequence

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!`

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
string getPermutation(int n, int k) {
string s = "", res = "";
for(int i = 1; i <= n; i++) s.push_back(i + '0');
string path = s;
int count = 0;
DFS(s, 0, count, n, k, path, res);
return res;
}

void DFS(string& s, int pos, int& count, int n, int k, string& path, string& res){
if(count >= k || pos == n){
if(++count == k) res = path;
return;
}
for(int i = 0; i < n; i++){
if(s[i] == '0') continue;
path[pos] = s[i];
s[i] = '0';
DFS(s, pos + 1, count, n, k, path, res);
s[i] = path[pos];
}
}
};
``````
Copy The Code &

Input

cmd
n = 3, k = 3

Output

cmd
"213"

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const getPermutation = function(n, k) {
const factorial = Array(n + 1).fill(0)
factorial[0] = 1
for(let i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i
}
let res = ''
const visited = Array(n + 1).fill(0)
dfs(0)
return res

function dfs(idx) {
if(idx === n) return

const cnt = factorial[n - idx - 1]
for(let i = 1; i <= n; i++) {
if(visited[i]) continue
if(cnt < k) {
k -= cnt
continue
}
res += i
visited[i] = 1
dfs(idx + 1)
return
}
}
};
``````
Copy The Code &

Input

cmd
n = 4, k = 9

Output

cmd
"2314"

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def getPermutation(self, n, k):
p = itertools.permutations(range(1, n + 1))
for i in range(k):
res = next(p)
return ''.join([str(i) for i in res])
``````
Copy The Code &

Input

cmd
n = 3, k = 1

Output

cmd
"123"

#4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
public class _060_PermutationSequence
{
public string GetPermutation(int n, int k)
{
var nums = new List();
var group = 1;
for (int i = 1; i <= n; i++)
{
group *= i;
}

if (k > group) return "";
k = k > 0 ? k - 1 : 0;

var result = new StringBuilder();
var index = -1;
while (n > 0)
{
group /= n;
index = k / group;
result.Append(nums[index]);
nums.RemoveAt(index);

k = k % group;
n--;
}

return result.ToString();
}
}
}
``````
Copy The Code &

Input

cmd
n = 3, k = 3

Output

cmd
"213"