解题思路

这题大概的代码与全排列(LC46)差不多,它们的区别是给定的nums中包含重复的元素，那么我们在遍历的时候要记录当前这层是否已经使用过某个元素了，如果已经使用过了则跳过。同样使用的是哈希表，不过这次记录的不是下标而是元素值。

代码

Python

1
2
3
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        return list(set(permutations(nums)))

C++

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
class Solution {
    vector<int> vis;

public:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

Go

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
var result [][]int
var path []int
func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    result = [][]int{}
    path = []int{}
    m := make(map[int]bool)
    backtracking(nums, m)
    return result
}

func backtracking(nums []int, m map[int]bool) {
    if len(path) == len(nums) {
        t := make([]int, len(path))
        copy(t, path)
        result = append(result, t)
    }
    uset := make(map[int]bool)
    for i := 0; i < len(nums); i++ {
        if m[i] == true {continue}
        if uset[nums[i]] == true {continue}
        m[i] = true
        uset[nums[i]] = true
        path = append(path, nums[i])
        backtracking(nums, m)
        path = path[:len(path) - 1]
        m[i] = false
    }
}