My recursive easy to understand code :D


  • 0
    N
    void solve(int n,int k,string &s,vector<bool> &used)
    {
        int pp = 0;
        for(int i=n;i>=1;i--){
            if(!used[i]){
                pp = i;
                break;
            }
        }
        if(pp==0)    return ;
        if(k==0){
            used[pp] = 1;
            s += (pp+'0');
            solve(n,0,s,used);
        }else{
            int ans = 1;
            for(int i=1;i<n-s.size();i++)    ans *= i;
            int p = k/ans;
            if(p and k%ans==0)   p--;
            int cnt = 0,i;
            for(i=1;i<=n;i++){
                if(used[i]) continue;
                if(cnt==p)    break;
                cnt++;
            }
            used[i] = 1;
            s += (i+'0');
            solve(n,k%ans,s,used);
        }
    }
    
    class Solution {
    public:
        string getPermutation(int n, int k) {
            string s = "";
            vector<bool> used(n+1,false);
            solve(n,k,s,used);
            return s;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.