这是我参与8月更文挑战的第13天，活动详情查看：8月更文挑战

前言

力扣第四十六题 全排列 如下所示：

给定一个不含重复数字的数组 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]]
复制代码

提示：

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

一、思路

题目中有两个比较重要的信息：

• nums 中的所有整数 互不相同
• 返回所有可能的 全排列

当我看到 全排列 这几个字眼，就很容易的联想到了使用 递归 来解决问题。

递归大概的思路分为以下几个部分：

1. 使用 栈 来保存当前路径
2. 递归：遍历数组，如果当前值不在路径中则 入栈。并继续往下递归
3. 如果 栈 的大小等于数组的长度，将当前路径加入到结果集，并结束此层递归

举个例子

此处以示例 1中的 nums = [1,2,3] 作为例子

1. i=0，nums[0] = 1 入栈，栈中的值为 1，并继续下一层递归
2. 递归1：因 nums[0] = 1 已在栈中存在，故跳过
3. 递归1：i=1，nums[1] = 2 入栈，栈中的值为 1 -> 2，并继续下一层递归
4. 递归2：因 nums[0] = 1 和 nums[1] = 2 已在栈中存在，故跳过
5. 递归2：i=2，nums[2] = 3 入栈，栈中的值为 1 -> 2 -> 3。此时 栈满，记录这一组结果，并将栈顶出栈，栈中的值为 1 -> 2
6. 递归2：遍历结束，向上回溯。并将栈顶出栈，栈中的值为 1
7. 递归1：i=2，nums[2] = 3 入栈，栈中的值为 1 -> 3，并继续下一层递归
8. 递归2：因 nums[0] = 1 已在栈中存在，故跳过
9. 递归2：i=1，nums[1] = 2 入栈，栈中的值为 1 -> 3 -> 2。此时 栈满，记录这一组结果
10. 其他的结果过程同上
11. 最终可以获得正确的结果集 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

二、实现

实现代码

实现代码与思路保持一致

    /**
     * 递归
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        dfs(ret, nums, stack);
        return ret;
    }

    public void dfs(List<List<Integer>> list, int[] nums, Stack<Integer> stack) {
        if (stack.size() == nums.length) {
            list.add(new ArrayList<>(stack));
            return;
        }
        for (int num : nums) {
            if (stack.contains(num))
                continue;
            stack.push(num);
            dfs(list, nums, stack);
            stack.pop();
        }
    }
复制代码

测试代码

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        new Number46().permute(nums);
    }
复制代码

结果

三、总结

我其实尝试在回溯和过程中取得到下一个应该选择的下标，但是我失败了 tnt~。
后来看到官方题解中是使用的交换数组内元素来避免寻找下一个插入的下标。非常不错的思路，值得学习！

感谢看到最后，非常荣幸能够帮助到你~♥