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:
"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!
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];
}
}
};
Input
n = 3, k = 3
Output
"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
}
}
};
Input
n = 4, k = 9
Output
"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])
Input
n = 3, k = 1
Output
"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 < int>();
var group = 1;
for (int i = 1; i < = n; i++)
{
nums.Add(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();
}
}
}
Input
n = 3, k = 3
Output
"213"