LeetCode.046.Permutations 全排列

题目描述

46 Permutations
https://leetcode-cn.com/problems/permutations/

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

---

解题过程

全排列问题是一个非常经典的 回溯法 backtracking 应用，全排列的代码可以直接作为回溯法的代码模板，非常值得一做的题目。
n 个数的全排列有 n! 个
对于第一个位置，可选的数有 n 个，第一个位置选择完毕后，第二个位置有 n-1 个选择，以此类推。
假如第一个位置选择 nums[0] ，并把所有其他位置选择完毕后，我们需要回退撤销第一个选择 nums[0] ，继续选择 nums[1] 放在第一个位置。

需要注意的地方：
1、满足结束条件 或 到达解空间叶子节点后，把当前选择加入结果集 resultSet 时，需要做一次拷贝，否则由于 Java 中的引用传递的是地址，后续操作会继续修改已经完成的选择，当然如果使用 String 则没有这个问题，使用其他集合类存储选择结果时都需要注意。
2、用 stack 存储当前选择，方便在末尾 push(选择) 和 pop(撤销)， LinkedList 实现了 Deque 接口，可当做栈使用。
3、我这里使用 Set 存储剩余可用选择，是一种很低效的浪费空间的做法，但方便理解，可以参考官方解法中的直接在原数组上用下标分隔已选和未选元素，并使用 Collections.swap 进行选择和撤销，或者，使用一个 boolean[] selected 数组标记是否选择过。

可以参考 liweiwei 这个全排列的题解，以全排列问题为切入点，全面介绍了回溯法，很详细
从全排列问题开始理解「回溯」算法（深度优先遍历 + 状态重置 + 剪枝）
https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

时间复杂度 O(n*n!)，空间复杂度O(n*n!)

private static class SolutionV2020 {
    private List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        if (null == nums || 0 == nums.length) {
            return Collections.emptyList();
        }
        res = new ArrayList<>();
        Set<Integer> choices = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        backtrace(new LinkedList<>(), choices);
        return res;
    }

    /**
     * 回溯
     * @param permute 当前的排列，用 stack 存储方便在末尾 push(选择) 和 pop(撤销)， LinkedList 实现了 Deque 接口，可当做栈使用
     * @param choices 当前可用的选择 集合
     */
    private void backtrace(LinkedList<Integer> permute, Set<Integer> choices) {
        if (choices.size() == 0) {
            // 剩余可用选择为0，结束，加入结果集
            res.add(new ArrayList<>(permute));
            return;
        }
        // 遍历选择列表
        for (Integer choice : new HashSet<>(choices)) {
            permute.push(choice); // 选择 choice 加入排列
            choices.remove(choice); // 把 choice 从剩余可用选择集合中删除
            backtrace(permute, choices); // 递归进行后续选择
            permute.pop(); // 回退撤销 choice 选择
            choices.add(choice); // 把 choice 恢复到剩余可用选择集合
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_046_Permutations.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_046_Permutations.java

---