class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<bool> st(10);//当前哪些数被用过了
        for (int i = 0; i < n; i ++ ) {
            //每填一个数，就会剩下n - i - 1个阶乘的情况，所以先求阶乘
            int fact = 1;
            for (int j = 1; j <= n - i - 1; j ++ ) fact *= j;

            for (int j = 1; j <= n; j ++ ) {
                if (!st[j]) {//第j个数没有被用过
                //判断是第k个数否在这个分支里，fact < k 说明这个分支一定在k的前面
                    if (fact < k) k -= fact;//那么就将k减去fact
                    else {
                        res += to_string(j);//第k个数的第i位应该填j
                        st[j] = true;//标记被用过了
                        break;//每一位只能填一个数，所以一定记得要break
                    }
                }
            }
        }
        return res;//返回答案
    }
};