题解 | 没有重复项数字的全排列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
             // 目标 ：没有重复项数字的全排列
        //例如：输入：[1,2,3]
        //输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
        //结论：用3重循环可以解决这个问题 第一层循环：1 2 3
        //第二层循环：对于第一层循环取1 只能遍历 2 3
        //第三层循环：对于第二层循环取2 ，第一层循环取1 只能取3
        //按照这个思路可以实现数组长度为3的没有重复项数字的全排列
        //由于输入参数nums的长度未知，因此我们用递归算法实现这个多重循环,
        //假设数组nums长度为n,一共需要n * n次判断
        //1、声明1个2维list2存储循环取值
        ArrayList<ArrayList<Integer>> list2 = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        dfs(num,new ArrayList<>());
        //8、结尾 把这个2维list2进行返回
        return list2;
    }
    //2、这个递归方法dfs的入参是：数组num 及 1维度list1
    void dfs(int[] nums,ArrayList<Integer> list1){
        //3、递归出口是list1.size() >= nums.length
        if(list1.size() >= nums.length){
             //4、满足这个递归出口条件 把list1存入list2 并结束这次递归
            list2.add(new ArrayList<>(list1));
            return;
        }
        //5、for循环遍历nums每个元素
        for(int i = 0;i < nums.length;i++){
            //6、判断list1是否为空，如果为空直接把nums[i]存入list1
            if(list1 == null || list1.size() == 0){
                list1.add(nums[i]);
            }else {
                if(list1.contains(nums[i])){
                //如果不为空，判断list1是否存在相同元素，如果存在相同元素
        //忽略本次循环后续步骤，并进行下次循环
                    continue;
                }else{
      //如果不存在相同元素把nums[i]存入list
                    list1.add(nums[i]);
                }
            }
             //并调用这个递归方法dfs,传入数组nums 当前1维数组list1 
            dfs(nums,list1);
                    //7、回退，例如现在list1为1 2 3 ，长度3个，进行到数组下标2
        //回退至位置 下标为1的位置 ，把下标为1的位置取值3并进行下次递归
            list1.remove(list1.size() - 1);

        }
    }
}