排列类型

# 46. 全排列 (opens new window)

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    boolean[] vis;
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        this.vis = new boolean[nums.length];
        dfs();
        return ret;
    }
    void dfs(){
        if(nums.length==path.size()){
            ret.add(new ArrayList<>(path));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(vis[i]) continue;
            vis[i] = true;
            path.add(nums[i]);
            dfs();
            vis[i] = false;
            path.remove(path.size()-1);
        }
    }
}

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

# 47. 全排列 II (opens new window)

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] vis;
    int[] nums;
    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        this.vis = new boolean[nums.length];
        Arrays.sort(nums);
        dfs();
        return ret;
    }
    void dfs(){
        if(nums.length==path.size()){
            ret.add(new ArrayList<>(path));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && !vis[i-1]){
                continue;
            }
            if(vis[i]) continue;
            vis[i] = true;
            path.add(nums[i]);
            dfs();
            vis[i] = false;
            path.remove(path.size()-1);
        }
    }
}

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

# 60. 排列序列 (opens new window)

← 子集类型树回溯→