【LeetCode】46. 全排列

一、题目描述

给定一个不含重复数字的数组 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 中的所有整数 互不相同

二、思路分析

这道题并不难，可以当作回溯算法的练习题。另外就是我感觉回溯和深度优先搜索是差不多的思想。

首先我可以从题目中获取一个非常重要的信息：这是一个不含重复元素的数组。 如果包含重复数字就要考虑会不会出现重复的排列。

当遇到无重复元素的排列这种题目的时候，不需要多想，就是简单暴力的去遍历每一种可能，就像小时候玩的选数字填空，假如使用1,2,3三个元素，那么我们就是在三个空位置上进行选数字，转化成图就是下面所示：

针对上面这个例子，我们可以直接三次循环走起，遍历出所有的结果就是答案。但是我们要考虑一个情况，随着数字越来越大，我们写循环的话，代码就会越套越多，越来越长，这简直快赶上套娃了。

那么是不是有更加优雅的写法呢？

这个肯定是有滴，我们从上面那个图可以看出来什么呢？这是不是一棵树，而排列的答案就是对树中每条路径的遍历，这个也就是对树的遍历，也就变成了使用回溯算法，写代码的形式也就变成了我们常说的递归。

这里有一个需要注意的点，全排列里面一个元素不能同时出现多次，那么我们就需要一个标记数组，用来记录已经使用过元素。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        backTrack(nums, new int[n], n);
        return result;
    }

    public void backTrack(int nums[], int[] status, int n) {
        if (list.size() == n) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (status[i] == 1) {
                continue;
            }
            list.add(nums[i]);
            status[i] = 1;
            backTrack(nums, status, n);
            list.removeLast();
            status[i] = 0;
        }
    }
}

三、总结

一般来说，递归和循环都是可以相互转化的，就看哪个理解和实现起来比较容易。

全排列这种题目，基本上就是暴力解法，没有投机取巧的说法。我们可以通过把题目信息分解转化成一棵树的形式，然后对树进行遍历获取最终的答案，这样更加容易理解这一类型的题目。