Java——全排列

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目链接

leetcode在线oj题——全排列

题目描述

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

题目示例

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

输入nums = [0,1]
输出[[0,1],[1,0]]

输入nums = [1]
输出[[1]]

题目提示

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

题目思路

我们可以使用回溯算法和深度优先遍历将所有的结果找到首先定义一个空的栈path还有一个布尔数组isUsed用来判断这个元素是否被添加过。如果被添加过该元素对应的下标对应的值置为true

按照数组的顺序先添加第一个元素1将isUsed[0]置为true然后添加第二个元素2将isUsed[1]置为true然后添加第三个元素3将isUsed[2]置为true

这时path已经满了我们就需要将这个满了的路径添加到List中将isUsed[2]置为false然后退回到上一个状态12将isUsed[1]置为false由于这个状态已经添加过3并且没有其他元素可以添加了因此再次退回到上一个状态1

这时我们的状态是在第三个元素上的因此添加3然后将isUsed[2]置为true然后添加2将isUsed[1]置为true这时我们的path长度和nums长度一致就需要退回到上一个状态

依次类推将所有的状态都添加到List中
在这里插入图片描述
稍后有详细的代码执行流程图

代码实现

class Solution {
    public static List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        if(len == 0){
            return lists;
        }

        Stack<Integer> path = new Stack<>();
        boolean[] isUsed = new boolean[len];
        dfs(nums,len,0,path,isUsed,lists);
        return lists;
    }

    private static void dfs(int[] nums, int len, int depth, Stack<Integer> path, boolean[] isUsed, List<List<Integer>> lists) {
        if(depth == len){
            lists.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if(isUsed[i]){
                continue;
            }
            path.add(nums[i]);
            isUsed[i] = true;
            dfs(nums,len,depth + 1 , path, isUsed, lists);
            isUsed[i] = false;
            path.pop();
        }
    }
}