# 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):

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"321"`

Given n and k, return the kth 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 k-th 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 k-th sequence of length n, basically let a[1]…a[n] denote the k-th sequence, think about this: except a[1] there are totally (n-1)! different permutations for a[2]…a[n], then a[1] = k / (n-1)! and we need to find k % (n-1)! -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 (n-1)! or 3 * (n-1)! sort of these cases. The following code is accepted by LeetCode OJ to pass this Permutation Sequence problem:

```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[i-1];
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[i-1] + 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.

Written on June 15, 2013