LeetCode Permutation Sequence: Math Approach Rather Than DFS
Overview
To solve LeetCode Permutation Sequence, math could be adopted to identify the correct number in the corresponding position rather than do DFS simulation.
LeetCode Permutation Sequence
The set [1,2,3,…,<i>n</i>]
contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"

"132"

"213"

"231"

"312"

"321"
Given n and k, return the k^{th} permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Solution Analysis: Math Approach Rather Than DFS
(1) DFS and enumerate all the sequences by the increasing order, when enumerate the kth sequence, return it. This would be TLE for large test case
(2) Actually there is “O(n)” solution. From pure mathematical view, for example we want to find kth sequence of length n, basically let a[1]…a[n] denote the kth sequence, think about this: except a[1] there are totally (n1)! different permutations for a[2]…a[n], then a[1] = k / (n1)! and we need to find k % (n1)! th element is the a[2]…[an] sequence, this is recursively the same problem. Just be careful when dealing with some border cases like k is exactly (n1)! or 3 * (n1)! sort of these cases. The following code is accepted by LeetCode OJ to pass this Permutation Sequence problem:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string getPermutation(int n, int k) {
string sol;
vector<char> nums;
int per[10];
per[0] = per[1] = 1;
for (int i = 1; i <= n; ++i) {
per[i] = i * per[i1];
nums.push_back('0' + i);
}
int v = 0;
for (int i = n; i >= 1; i) {
v = (k  1) / per[i  1];
sol.push_back(nums[v]);
nums.erase(nums.begin() + v);
k = (k  1) % per[i1] + 1;
}
return sol;
}
And not that the real time complexity is O(N^2) because erase operation takes O(N) time, I say this is a “O(N)” approach in a sense of that it just linear scan the permutation to generate the final result.
Summary
To solve LeetCode Permutation Sequence, math could be adopted to identify the correct number in the corresponding position rather than do DFS simulation.