博客

每日一题

Java-全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]

输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]

输出：[[1]]

class Solution {

    public static List<List<Integer>> permute(int[] nums){
        boolean[] isVisited = new boolean[nums.length];
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums,0,isVisited,path,res);
        return res;
    }

    public static void dfs(int[] nums,int depth, boolean[] isVisited,List<Integer> path,List<List<Integer>> res){
        int length = nums.length;
        if(depth == length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < length; i++) {
            if(!isVisited[i]){
                isVisited[i] =true;
                path.add(nums[i]);
                depth++;
                dfs(nums,depth,isVisited,path,res);
                //下面开始回溯
                isVisited[i] = false;
                //depth--;
                //有好几个for循环，在第一次选择根节点1时是第一个for，在选择1下面的一个根节点时是第二个for，
                // 此时进行的是值传递，所以在根节点的for上depth是1没有变，以此类推
                path.remove(path.size()-1);
            }
        }
    }
    
}