class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<bool> st(10); //记录哪些数字被用过了
        for (int i = 0; i < n; i ++) { //从第0位开始直到第n-1位 (共n位)
            int fact = 1;
            for (int j = 1; j < n - i; j ++) fact *= j; //每填一个数都会有(n-i-1)！个数，供“消耗k”，直到将k消耗成0为止
            for (int j = 1; j <= n; j ++) { //枚举没有被用过的数
                if (!st[j]) { //当j没有被用过，才做操作，j如果已被固定，直接看下一个没有被用过的数
                    if (fact >= k) { //说明当前数j应该在这个分支里
                        res += to_string(j); //当前位选用j
                        st[j] = true; //j已经被选择了，所以应置为true
                        break;//当确定某一位，就可以跳出循环了，再看接下来一位填几
                    }
                    k -= fact; //说明当前分支，不能供k消耗，看下一位要填的是否满足
                }
            }
        } 
        return res;
    }
};