LeetCode热题100——46. 全排列

https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-100-liked

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

题解

使用树形结构来排列，减掉不符合要求的枝丫，再回溯到上一个元素继续遍历

public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(nums, res, path);
        return res;
    }

    private  void dfs(int[] nums, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == nums.length) {
            // 注意这里要new一个集合把原来的数据拷贝到新集合
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 减枝, 如果出现过某个元素直接遍历下一个
            if (path.contains(nums[i])) continue;
            path.add(nums[i]);
            dfs(nums, res, path);
            path.remove(path.size() - 1);
        }
    }

复杂度

时间复杂度 O(n*n!)
全排列的每条路一共 n!，每次 递归内部 new ArrayList<>(path) 或者 path.contains(nums[i]) 要n次，所以一共是 O(n * n!)

空间复杂度 O(n)
如果只输出而不保存所有结果（使用回溯+原地交换）：
递归栈深度为 n，每层一个调用，空间复杂度为：O(n)。

如果保存所有结果到列表中：
需要存储 n! 个排列，每个排列长度为 n，所以是：
空间复杂度为：O(n × n!)。