LeetCode 60. 第k个排列

解题思路

这道题的做法和全排列的做法基本一致。

相关代码

class Solution {
    int t=1;  //表示的是第几个排列
    String s="";
    List<Integer> path;
    boolean st[];
    public String getPermutation(int n, int k) {
        path = new ArrayList<>();
        st = new boolean[n];
        int a[] = new int[n];
        for(int i=0;i<n;i++) a[i] = i+1;
        dfs(a,0,k,path);
        return s;
    }
    //u表示的是已经选择了u-1+1个数，目前开始选第u个数。
    //也可以理解成层数
    public void dfs(int a[],int u,int k,List<Integer> path){
        if(u==a.length){
            if(t==k)
                for(int i=0;i<path.size();i++) s=s+path.get(i);
                t++;
                return;
        }
        for(int i=0;i<a.length;i++)
            if(st[i]==false){
                st[i] = true;
                path.add(a[i]);
                dfs(a,u+1,k,path);
                path.remove(path.size()-1);
                st[i] = false;
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32