全排列

问题陈述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例：

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,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
class Solution{
    public List<List<Integer>> permute(int[] nums){
        int len=nums.length;
        List<Integer> path=new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        boolean[] visited=new boolean[len];
        if(len==0) return null;
        dfs(nums,len,0,path,visited,res);
        return res;
        
    }
    public void dfs(int[] nums,int len,int depth,List<Integer> path,boolean[] visited,List<List<Integer>> res){
        if(depth==len){
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!visited[i]){
                path.add(nums[i]);
                visited[i]=true;
                dfs(nums,len,depth+1,path,visited,res);//递归下一层
                visited[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
31
32
class Solution {
    //主函数
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutelist=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        backtrack(nums,permutelist,list,visited);
        return permutelist;
    }

    private void backtrack(int[] nums,List<List<Integer>> permutelist,List<Integer> list,boolean[] visited){
        //加入满足条件的结果。
        if(list.size()==nums.length){
            permutelist.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            //删除不合法的选择
            if(visited[i]){
                continue;
            }
            //做选择
            visited[i]=true;
            list.add(nums[i]);
            //进入下一层决策树
            backtrack(nums,permutelist,list,visited);
            //撤销选择
            list.remove(list.size()-1);
            visited[i]=false;
        }
    }
}

全排列Ⅱ

给定一个可包含重复数字的序列，返回所有不重复的全排列。

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。

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
33
34
35
36
37
38
class Solution {
    //主函数
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> permutelist=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        Arrays.sort(nums);//排序
        boolean[] visited=new boolean[nums.length];
        backtrack(nums,permutelist,list,visited);
        return permutelist;
    }

    private void backtrack(int[] nums,List<List<Integer>> permutelist,List<Integer> list,boolean[] visited){
        //加入满足条件的结果。
        if(list.size()==nums.length){
            permutelist.add(new ArrayList<>(list));
            return;
        }
      
        for(int i=0;i<nums.length;i++){
            //跳过重复
            if(i!=0 && nums[i]==nums[i-1] && !visited[i-1]){
                continue;
            }
            //删除不合法的选择
            if(visited[i]){
                continue;
            }
            //做选择
            visited[i]=true;
            list.add(nums[i]);
            //进入下一层决策树
            backtrack(nums,permutelist,list,visited);
            //撤销选择
            list.remove(list.size()-1);
            visited[i]=false;
        }
    }
}