[LeetCode] Permutation Sequence

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
int factorial(int n) {
return n == 1 ? 1 : n * factorial(n-1);
}
string helper(int n, int k) {
if(n == 1) return string(1, '0' + k);
int comb = factorial(n-1);

int front = (k - 1) / comb;
return string(1, '1' + front) + helper(n-1,k - front * comb);
}
public:
string getPermutation(int n, int k) {
string res = helper(n,k);

for(int num = 1; num <= n; num++) {
for(int i = 0; i < res.length(); i++) {
if((res[i] & 0b1111) == num) {
for(int j = i + 1; j < res.length(); j++)
if(res[j] >= res[i]) res[j]++;
break;
}

}
}

return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/04/01/PS/LeetCode/permutation-sequence/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.