【46】全排列

1. 题目描述

2. 题目链接

https://leetcode.cn/problems/permutations/

3. 思路

这个问题可以看作有个排列成一行的空格，我们需要从左往右依此填入题目给定的个数，每个数只能使用一次。那么最直接的一种方法，就是从左往右每一个位置都依此尝试填入一个数，看能不能填完这个空格，在程序中我们可以用「回溯法」来模拟这个过程。

我们定义递归函数表示从左往右填到第个位置，当前排列为。 那么整个递归函数分为两个情况：

• 如果，说明我们已经填完了个位置（注意下标从开始），找到了一个可行的解，我们将放入答案数组中，递归结束。

• 如果，我们要考虑这第个位置填哪个数。根据题目要求我们不能填已经填过的数，因此我们填充一个之前没有填过的数，然后继续填下一个位置，即调用函数。回溯时要撤销这一个位置填的数及标记并继续尝试其他没被标记过的数。

如何判断数字是否填充过？
我们可以将题目给定的个数的数组划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。

具体来说，假设我们已经填到第个位置，那么数组中是已填过的数的集合，是待填的数的集合。我们肯定是尝试用里的数去填第个数，假设待填的数的下标为，那么填完后我们将第个数和第个数交换，即能使得在填第个数时数组的部分为已填过的数，为待填的数，回溯时交换回来即能完成撤销操作。

下图展示了回溯的整个过程：

4. 代码实现

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> output = new ArrayList<>();
    for (int num : nums) {
        output.add(num);
    }
    backtrack(nums.length, 0, output, ans);
    return ans;
}
private void backtrack(int n, int first, List<Integer> output, List<List<Integer>> ans) {
    // 所有的数都填完了
    if (first == n) {
        ans.add(new ArrayList<>(output));
        return;
    }
    for (int i = first; i < n; i++) {
        // 动态维护下一个数
        Collections.swap(output, i, first);
        backtrack(n, first + 1, output, ans);
        // 回溯，再把顺序交换回来
        Collections.swap(output, i, first);
    }
}

• 时间复杂度：，其中为序列的长度。算法的复杂度首先受的调用次数制约，的调用次数为次，其中，该式被称作 n 的 k - 排列。而，这说明的调用次数是的。而对于调用的每个叶结点（共个），我们需要将当前答案使用的时间复制到答案数组中，相乘得时间复杂度为。

• 空间复杂度：，其中为序列的长度。除答案数组外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，可知递归调用深度为。

  【47】全排列Ⅱ

  1. 题目描述

  

  2. 题目链接

  https://leetcode.cn/problems/permutations-ii/

  3. 思路

  此题是「46. 全排列」的进阶，序列中包含了重复的数字，并要求我们返回不重复的全排列，那么我们依然可以选择使用搜索回溯的方法来做。但相比「46. 全排列」的做法，我们不能再将数组划分成左右两个部分以此来判断数字是否填充过了。因为我们需要维护顺序性，用于过滤掉重复元素。

我们定义一个标记数组来标记已经填过的数，在填第个数的时候，我们遍历题目给定的个数，如果这个数字没有被标记过，我们就尝试填入并将其标记，然后继续尝试填下一个位置。当回溯时要撤销该位置填的数以及标记，并继续尝试其他没被标记过的数。

但是单纯采用这种方式并不能满足「全排列不重复」 的要求，在递归函数中我们会生成大量重复的排列，因为对于第的位置，如果存在重复的数字，我们每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复，因此我们需要处理这个情况。

要解决重复问题，我们只要设定一个规则，保证在填第个数的时候重复数字只会被填入一次即可。为此，我们选择对原数组升序排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」。即如下的判断条件：

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;
}

这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。为什么能够这样保证呢？是用来判断元素是否重复的，我们这里重点解释一下 !used[i - 1] 的作用：

加上 !used[i - 1] 来去重主要是用来限制两个相邻重复数字的访问顺序。假设有两个重复的数字，如果我们不去重，会有两种重复排列，但实际上我们只需要取其中任意一种排列即可。为此，我们需要限制一下的访问顺序。假设我们只需要取那个排列的话，则要求我们只有先访问了（nums[i-1]）之后才能去访问（nums[i]），而如果 !used[i-1] 成立，则表示我们还没有访问时就想要访问，此时我们就需要跳过这个排列。

以数组为例，回溯的具体过程如下图所示：

得到的全排列是：。特点是：，即出现的顺序只能是先后。

4. 代码实现

public static List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    // 排序，排序是剪枝的前提
    Arrays.sort(nums);
    // 用来标记已填充的数字
    boolean[] used = new boolean[nums.length];
    backtrack(0, nums, used, new ArrayList<>(), ans);
    return ans;
}
private static void backtrack(int idx, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
    if (idx == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 不能重复选择同一个数字
        if (used[i]) {
            continue;
        }
        // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 选择当前元素
        path.add(nums[i]);
        used[i] = true;
        // 递归寻找下一个元素
        backtrack(idx + 1, nums, used, path, ans);
        // 回溯
        used[i] = false;
        path.remove(path.size() - 1);
    }
}