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 (ie, for n = 3):

    "123"

    "132"

    "213"

    "231"

    "312"

    "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

class Solution {

public:

    string getPermutation(int n, int k) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        int A[] = {,, , , , , , , };

        string    res = "";

        vector<bool> flag(n+, false);

        for(int i = n-; i >= ; --i)

        {

            int pos = k / A[i];

            if(k%A[i] == && pos > ) --pos;

            k = k - pos * A[i];

            for(int j = ; j <= n; ++j)

            {

                if(flag[j] == false){

                    if(pos == )

                    {

                        char c = '' + j;

                        res += c;

                        flag[j] = true;

                        break;

                    }else{

                        --pos;

                    }

                }

            }

        }

        return res;

    }

};