Permutation Sequence
Post
Cancel

# LeetCode #60: Permutation Sequence (C/C++).

hard

source: https://leetcode.com/problems/permutation-sequence/
C/C++ Solution to LeetCode problem 60. Permutation Sequence.

## Problem

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:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

## Examples

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

## Solution

We can generate k! permutations, but this is not an optimal solution, so:

• Let’s consider the case for n = 4 and k = 14.
• We know there are 24 permutations (n!).
• Because the numbers are in sequence from 1 to n, we have the next permutations:
• 1 + permutations of {2, 3, 4} -> (3! = 6) -> (1234, 1243, 1324, 1342, 1423, 1432) -> Permutations 1 to 6
• 2 + permutations of {1, 3, 4} -> (3! = 6) -> (2134, 2143, 2314, 2341, 2413, 2431) -> Permutations 7 to 12
• 3 + permutations of {1, 2, 4} -> (3! = 6) -> (3124, 3142, 3214, 3241, 3412, 3421) -> Permutations 13 to 18
• 4 + permutations of {1, 2, 3} -> (3! = 6) -> (4123, 4132, 4213, 4231, 4312, 4321) -> Permutations 19 to 24
• From the previous, we know that the 14th permutation (k = 14) starts with 3, so we are at the 13th permutation.
• Then to calculate the next number we repeat the process with the rest of the numbers:
• 1 + permutations of {2, 4} -> (2! = 2) -> (124, 142) -> Permutations 13 to 14
• 2 + permutations of {1, 4} -> (2! = 2) -> (214, 241) -> Permutations 15 to 16
• 4 + permutations of {1, 2} -> (2! = 2) -> (412, 421) -> Permutations 17 to 18
• From the previous, we know the next number is 1, so, we repeat the process:
• 2 + permutation of {4} -> (1! = 1) -> (24) -> Permutations 13.
• 4 + permutation of {2} -> (1! = 1) -> (42) -> Permutations 14.
• From the previous, we know the next number is 4, so, we repeat the process:
• 2 + permutation of {} -> (0! = 1) -> (2) -> Permutations 14.
• From the previous, we know the next number is 2. There are no more numbers left, so, the algorithm ends.

The 14th permutation is: 3142.

### Solution

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 class Solution { public: string getPermutation(int n, int k) { string permutation = ""; vector<bool> v(n+1,false); vector<int> f(n+1, 1); for (int i = 2; i <= n; i++) f[i] = f[i-1] * i; k--; for(int i = 1; i <= n; i++){ int x = k/f[n-i]; int j; k -= x * f[n-i]; for(j = 1; j <= n; j++) { if (!v[j] && x==0) break; if (!v[j]) x--; } if (j<=n) v[j] = true; permutation += to_string(j); } return permutation; } };