欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯5.排列序列

程序员文章站 2022-05-21 23:21:55
...

返回第k个序列,序列是共有n个元素的集合中的全排列

首先这是一个排列问题,用used,然后序列中没有重复的元素,只是对集合进行排列而已,当进行到第k个时候直接返回即可。

class Solution {
    String res="";
    int count=1;
    public String getPermutation(int n, int k) {
        boolean[] used=new boolean[n];
        StringBuffer buffer = new StringBuffer();
        core(n,k,used,buffer,0);
        return res;
    }
    public void core(int n,int k,boolean[] used,StringBuffer temp,int depth){
        if(res!=""){
            return; //依靠这个来摆脱到k之后的回溯。
        }
        if(depth==n){
            if(count==k){
                res=temp.toString(); //到k则给res赋值
            }else{
                count++;  
                                                                                           //不到k则count++,但不用管s             
            }
            return;  //到k就要return
        }
        for(int i=0;i<n;i++){//i从0到n,有n个分支
            if(!used[i]){//没有遍历过才进入
                temp.append(i+1);
                used[i]=true;
                core(n,k,used,temp,depth+1);
                temp.deleteCharAt(temp.length() - 1);
                used[i]=false;
            }
        }
    }
}