题目链接

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，然后退回到上一个状态（1，2），将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();
        }
    }
}

可以放大一点看整个递归的过程