题目

力扣题目链接

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

  1. 输入：nums = [1,2,3]
  2. 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

  1. 输入：nums = [0,1]
  2. 输出：[[0,1],[1,0]]

示例 3：

  1. 输入：nums = [1]
  2. 输出：[[1]]

提示：

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

思路

此时我们已经学习了组合问题、分割问题和子集问题，接下来看一看排列问题。

相信这个排列问题就算是让你用 for 循环暴力把结果搜索出来，这个暴力也不是很好写。

所以正如我们在 回溯算法理论基础 所讲的为什么回溯法是暴力搜索，效率这么低，还要用它？

因为一些问题能暴力搜出来就已经很不错了！

我以[1,2,3]为例，抽象成树形结构如下：
image.png

回溯三部曲

1、递归函数参数

首先排列是有序的，也就是说[1,2] 和[2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素 1 在 [1,2] 中已经使用过了，但是在 [2,1] 中还要在使用一次 1 ，所以处理排列问题就不用使用 startIndex 了。

但排列问题需要一个 used 数组，标记已经选择的元素，如图橘黄色部分所示：
image.png

代码如下：

  1. int[] nums = null;
  2. boolean[] used;  // 排列问题需要一个 used 数组，标记已经选择的元素
  4. List<List<Integer>> result = new ArrayList<>();
  5. LinkedList<Integer> path = new LinkedList<>();
  7. void backtracking()

2、递归终止条件

image.png
可以看出叶子节点，就是收割结果的地方。

那么什么时候，算是到达叶子节点呢？

当收集元素的数组 path 的大小达到和 nums 数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

代码如下：

  1. if (path.size() == nums.length) {
  2.     result.add(new ArrayList<>(path));
  3.     return;
  4. }

3、单层搜索的逻辑

这里和组合问题、切割问题和子集问题最大的不同就是 for 循环里不用 startIndex 了。

因为排列问题，每次都要从头开始搜索，例如元素 1 在 [1,2] 中已经使用过了，但是在 [2,1] 中还要再使用一次1。

而 used 数组，其实就是记录此时 path 里都有哪些元素使用了，一个排列里一个元素只能使用一次。

代码如下：

  1. for (int i = 0; i < nums.length; i++) {
  2.     if (used[i]) { // path里已经收录的元素，直接跳过
  3.         continue;
  4.     }
  6.     path.add(nums[i]);
  7.     used[i] = true;
  9.     backtracking();
  11.     path.removeLast();
  12.     used[i] = false;
  13. }

那么就不难写出答案了。

总结

大家此时可以感受出排列问题的不同：

  • 每层都是从 0 开始搜索而不是 startIndex
  • 需要used数组记录path里都放了哪些元素了

排列问题是回溯算法解决的经典题目，大家可以好好体会体会。

答案

Java

  1. class Solution {
  2.     int[] nums = null;
  3.     boolean[] used;  // 排列问题需要一个 used 数组，标记已经选择的元素
  5.     List<List<Integer>> result = new ArrayList<>();
  6.     LinkedList<Integer> path = new LinkedList<>();
  8.     public List<List<Integer>> permute(int[] nums) {
  9.         this.nums = nums;
  10.         used = new boolean[nums.length];
  12.         backtracking();
  13.         return result;
  14.     }
  16.     void backtracking() {
  17.         // 当收集元素的数组 path 的大小达到和 nums 数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。可以看出叶子节点，就是收割结果的地方
  18.         if (path.size() == nums.length) {
  19.             result.add(new ArrayList<>(path));
  20.             return;
  21.         }
  23.         // 首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
  24.         // 元素 1 在 [1,2] 中已经使用过了，但是在 [2,1] 中还要在使用一次 1 ，所以处理排列问题就不用使用 startIndex 了。
  25.         for (int i = 0; i < nums.length; i++) {
  26.             // 如果该元素已被使用过, 则跳过
  27.             if (used[i]) {
  28.                 continue;
  29.             }
  30.             // 其实本题也可以不使用 used ，通过判断 path 中是否存在数字，排除已经选择的数字也是可以的
  31. //            if (path.size() == nums.length) {
  32. //                result.add(new ArrayList<>(path));
  33. //            }
  35.             path.add(nums[i]);
  36.             used[i] = true;
  38.             backtracking();
  40.             path.removeLast();
  41.             used[i] = false;
  42.         }
  43.     }
  44. }

REF

https://programmercarl.com/0046.全排列.html
https://leetcode-cn.com/problems/permutations/