Appearance
60. 排列序列
原题链接：LeetCode 60. 排列序列
题目描述
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
- 输入： n = 3, k = 3
- 输出： "213"
示例 2：
- 输入： n = 4, k = 9
- 输出： "2314"
示例 3：
- 输入： n = 3, k = 1
- 输出： "123"
提示：
- 1
- 1
难度： Hard
题解代码
javascript
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
let stop = false
let target = ''
var getPermutation = function(n, k) {
stop = false
target = ''
const used = Array(n).fill(false)
const ret = []
backTrack(n, [], ret, k, used)
return target
};
function backTrack (n, path, ret, k, used) {
if (path.length === n) {
ret.push(path.join(''))
if (ret.length === k) {
stop = true
target = ret[k - 1]
}
}
for (let i = 1; i < n + 1; i++) {
if (stop) continue
if (!used[i]) {
path.push(i)
used[i] = true
backTrack(n, path, ret, k, used)
path.pop()
used[i] = false
}
}
}