class Solution {
public:
    vector<vector<int>> ans;
    vector<int> corke;
    bool st[10];
    void dfs(int n,int x){
        if(x == n){
            ans.push_back(corke);
            return ;
        }
        for(int i=1;i<=n;i++){
            if(!st[i]){
                corke.push_back(i);
                st[i] = true;
                dfs(n, x + 1);
                corke.pop_back();
                st[i] = false;
            }
        }
    }
    string getPermutation(int n, int k) {
        dfs(n,0);
        // 竟然要字符串，可恶；
        string s = "";
        for(int i=0;i<n;i++){
            s += ans[k-1][i] + '0'; 
        }
        return s;
    }
};

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> fact(n+1, 1);
        for(int i = 2;i <= n;i ++){
            fact[i] = fact[i-1] * i;
        }
        string ans = "";
        vector<int> bs(n + 1 , 0);
        for(int i = 0;i < n;i ++){
            int st = fact[n-i-1];
            for(int j = 1;j <= n;j ++){
                if(bs[j]) continue;
                if(k > st) k -= st;
                else{
                    ans += j + '0';
                    bs[j] = 1;
                    break;
                }
            }
        }
        return ans;
    }
};