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

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <-– k = 17
3421
4123
4132
4213
4231
4312
4321

3124
3142
3214
3241
3412 <-– k’ = 4
3421

3412 <-– k’’ = 0
3421

3412 <-– k’’’ = 0

a1 = k / (n - 1)!
k1 = k

a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!

an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!

an = kn-1 / 0!
kn = kn-1 % 0!

``````class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
--k;
for (int i = n; i >= 1; --i) {
int j = k / f[i - 1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/60

Next Permutation

Permutations

https://leetcode.com/problems/permutation-sequence/

https://leetcode.com/problems/permutation-sequence/discuss/22508/An-iterative-solution-for-reference

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation