题目描述

给出一组数字，返回该组数字的所有排列例如： [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. （以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 $0 < n \le 6$

题目分析

获取数字的所有排列是一个典型的dfs问题，使用一个列表记录排列的数字，获取排列的过程就是不断在数组中选择数字的过程，从第一个数字开始直到最后一个数字被选择完后，列表即为排列结果，因为数字的排列一共有n!种情况，如图：

alt

因为数字是不能被重复选择的，所以需要记录下之前选过的数字，才能在后面选择中跳过。 dfs模板为：

dfs(int[] num, int start, List<Integer> path) {
 // 递归终止条件
  if(start == num.length){
  		//增加一种排列结果
        return;
  }
  for(int i=0;i<num.length;i++){
  // 对num中的数字进行选择
  		if(num[i]没有被选择过){
            // 选择num[i]
            // 撤销选择
        }
  }
}

解题思路

方法1：dfs递归回溯，使用set记录位置数字是否被访问过，list记录访问的数字

在判断数字是否被访问时，可以使用set来保存访问过的数字，后面在选择时，只要判断set是否包含即可。不过在做了回溯到上一步的时侯，需要取消选择，set也要删除之前选择的数字。

方法2：dfs递归回溯，使用交换法获得序列

除了基本的一个个数字进行选择方法外，还可以基于原数组，对两个数字位置进行交换得到不同的排列，因为没有重复项数字，只需要遍历所有数字的交换情况即可，交换的思路与选择类似，需要确定要交换的数字位置，不过每次交换不需要都从0的位置开始遍历，前面位置的情况遍历完后，下一次直接从该位置的后一位开始，即在循环中，修改两个地方：

①for循环的 i 初始值为start；

②dfs下一个递归从start+1（作为交换的确定的一个数字位置）后开始；

交换数字后有一个缺点，会导致添加情况的顺序不按照字典序的顺序，可以借助collections.sort()方法进行二维列表的排序。

代码实现

方法1：dfs递归回溯，使用set记录位置数字是否被访问过，list记录访问的数字

    ArrayList<ArrayList<Integer>> res;
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num);
        res = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        dfs(num, 0, set, new ArrayList<Integer>());
        return res;
    }
     
    public void dfs(int[] num, int start, HashSet<Integer> set, ArrayList<Integer> path){
        if(path.size() == num.length){
            // 枚举了所有数后，将该结果保存
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<num.length;i++){
            // 若是已经存储该数字（下标），或者重复的数字中前一个数字没有访问过（说明是以后面为开始访问到前面的数是重复情况）
            if(set.contains(i)){
                continue;
            }
            // 选择数字
            set.add(i);
            path.add(num[i]);
            // set记录从i+1下标开始
            dfs(num, i+1, set, path);
            // 撤销选择
            set.remove(i);
            path.remove(path.size()-1);
        }
    }

时间复杂度： $O (n n!)$ ，对于数字的排列情况一共有n!种，而在挑选数字的方法中需要对n个数字依次进行遍历，所以时间复杂度为 $O (n n!)$ ；

空间复杂度： $O (n)$ ，在遍历的过程中需要使用额外的set来存储数字下标，最多存储n个数字，同时还需要使用n大小的递归栈空间。

方法2：dfs递归回溯，使用交换法获得序列

    ArrayList<ArrayList<Integer>> res;
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num);
        res = new ArrayList<>();
        // 默认的数字排列
        ArrayList<Integer> path = new ArrayList<>();
        for(int i=0;i<num.length;i++){
            path.add(num[i]);
        }
        dfs(num, 0, path);
        // 交换位置后的列表，需要重新排序
        Collections.sort(res, new Comparator<ArrayList<Integer>>(){
            public int compare(ArrayList<Integer> list1, ArrayList<Integer> list2){
                for(int i=0;i<list1.size();i++){
                // 依次比较数字大小
                    if(list1.get(i) > list2.get(i)){
                        return 1;
                    }else if(list1.get(i) < list2.get(i)){
                        return -1;
                    }
                }
                return 1;
            }
        });
        return res;
    }
    
    public void dfs(int[] num, int start, ArrayList<Integer> path){
        if(start == num.length){
            // 枚举了所有数后，将该结果保存
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=start;i<num.length;i++){
            // 交换数字的位置
            swap(path, i, start);
            // 交换需要从start+1处往后
            dfs(num, start+1, path);
            // 撤销交换
            swap(path, i, start);
        }
    }
    
    public void swap(ArrayList<Integer> path, int index1, int index2){
        int tmp = path.get(index1);
        path.set(index1, path.get(index2));
        path.set(index2, tmp);
    }

时间复杂度： $O (n n! + n^{2} l o g n)$ ，对于数字的排列情况一共有n!种，而在挑选数字的方法中需要对n个数字依次进行遍历，在获得所有的排列后，还需要进行排序（collections默认是合并排序），时间消耗为 $n^{2} l o g n$ ；

空间复杂度： $O (n)$ ，在遍历的过程中使用了存储所有数字的列表path，后面都在这个列表上进行数据交换，同时还需要使用n大小的递归栈空间。

题解 | NC43 #没有重复项数字的所有排列#

题目描述

题目分析

解题思路

代码实现