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

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

# Solution

Approach 1: Level-by-level.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
private:
    vector<bool> bitMap;
    int getFactorial(int n) {
        if (n <= 1) return 1;
        return n * getFactorial(n - 1);
    }
    void getPermutation(int n, int k, string& seq) {
        if (n == 0)
            return;
        int f = getFactorial(n - 1);
        int i = (k - 1) / f;
        int j = -1;
        for (int k = 0; k <= i; ++k)
        {
            j++;
            while (bitMap[j])
                j++;
        }
        bitMap[j] = true;
        seq += ('1' + j);
        getPermutation(n - 1, (k - 1) % f + 1, seq);
    }
public:
    string getPermutation(int n, int k) {
        string seq = "";
        bitMap = vector<bool>(n, false);
        getPermutation(n, k, seq);
        return seq;
    }
};
class Solution {
public:
    string getPermutation(int n, int k) {
        ostringstream seq;
        vector<int> nums;
        int f = 1;
        for (int i = 1; i <= n; ++i)
        {
            nums.push_back(i);
            f *= i;
        }
        for (int i = n; i >= 1; --i)
        {
            f /= i;
            int pos = (k - 1) / f;
            seq << nums[pos];
            nums.erase(nums.begin() + pos);
            k = (k - 1) % f + 1;
        }
        return seq.str();
    }
};