问题描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

回溯

核心思路

这道题目和leetcode 46.全排列的区别在与给定序列可包含重复数字。

leetcode 40.组合总和 II和leetcode 90.子集 II分别讨论的是组合问题和子集问题的去重。

实际上，排列问题去重也是一样的套路。

要先对元素进行排序，以方便通过相邻的节点来判断是否重复使用。

对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

实现要点

如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

  • 时间复杂度：O(n×n!)O(n \times n!)，其中 nn 为序列的长度。

    算法的复杂度首先受 backtrack\textit{backtrack} 的调用次数制约，backtrack\textit{backtrack} 的调用次数为 ∑k=1nP(n,k)\sum_{k = 1}^{n}{P(n, k)} 次，其中 P(n,k)=n!(n−k)!=n(n−1)…(n−k+1)P(n, k) = \frac{n!}{(n - k)!} = n (n - 1) \ldots (n - k + 1)，该式被称作 n 的 k - 排列，或者部分排列。而 ∑k=1nP(n,k)=n!+n!1!+n!2!+n!3!+…+n!(n−1)!<2n!+n!2+n!22+n!2n−2<3n!\sum_{k = 1}^{n}{P(n, k)} = n! + \frac{n!}{1!} + \frac{n!}{2!} + \frac{n!}{3!} + \ldots + \frac{n!}{(n-1)!} < 2n! + \frac{n!}{2} + \frac{n!}{2^2} + \frac{n!}{2^{n-2}} < 3n!

    这说明 backtrack\textit{backtrack} 的调用次数是 O(n!)O(n!) 的。

    而对于 backtrack\textit{backtrack} 调用的每个叶结点（共 n!n! 个），我们需要将当前答案使用 O(n)O(n) 的时间复制到答案数组中，相乘得时间复杂度为 O(n×n!)O(n \times n!)。

    因此时间复杂度为 O(n×n!)O(n \times n!)。

  • 空间复杂度：O(n)O(n)，其中 nn 为序列的长度。我们需要 O(n)O(n) 的标记数组，同时在递归的时候栈深度会达到 O(n)O(n)，因此总空间复杂度为 O(n+n)=O(2n)=O(n)O(n + n)=O(2n)=O(n)。