60. 排列序列

直达叶节点，大量剪枝

class Solution {
    //观察得知，用dfs来做的，“节点”总数在10个左右
    String ans=new String();
    int[] data=new int[10];
    boolean[] used;
    public String getPermutation(int n, int k) {
       used=new boolean[n+1];
       calculate();
       dfs(n,k,1,"");
       return ans;  
    }
    void dfs(int n,int k,int cnt,String str){//cnt是已选数字个数。根据未选个数计算叶子结点个数。未选个数的阶乘就是叶子结点个数
    if(str.length()==n){
        ans=str;
        return;
    }
    
      for(int i=1;i<=n;i++){
          if(used[i])continue;
        int k1=n-cnt;//未选个数k1
        int k2=data[k1];//计算当前的叶子节点数
        //如果当前叶子节点个数小于k,跳过这个数字，找下一个
        if(k2<k){
          k-=k2;
          continue;
         }      
        //这里，k<k2.
          used[i]=true;
         dfs(n,k,cnt+1,str+i); 
         //return;
      }
    }
    void calculate(){
      data[0]=1;
      int base=1;
      for(int i=1;i<=9;i++){
         base*=i;
         data[i]=base;
      }
    }
}

60. 排列序列

原文：https://www.cnblogs.com/wsshub/p/14701502.html