47. Permutations II

Problem

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

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

Example 1:

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

Example 2:

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

Constraints:

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

Test Cases

1 2	class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([1,1,2], [[1,1,2], [1,2,1], [2,1,1]]),
    ([1,2,3], [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    assert sorted(sol.permuteUnique(nums.copy())) == sorted(expected)

Thoughts

46. Permutations 的进阶版，可以有重复元素，但结果排列要去重。

首先对 nums 排序，这样相同的数字会相邻在一起。然后先照搬 problem 46 的代码，在对重复数字做处理。

在 problem 46 中用集合记录待排列的数字，但本题中因为有重复就不能用了。可以改成字典（key 为数字，值为词频），或者就要有序的数组。给当前位置选数字的时候，从各不相同的数字中选取（即相同的多个数字只选一次）即可。

时间和空间复杂度是类似的。

Code

solution.py

class Solution:
    def permuteUnique(self, nums: list[int]) -> list[list[int]]:
        result = []

        def backtrack(remains: list[int]) -> None:
            if not remains:
                result.append(path.copy())
                return

            for i, num in enumerate(remains):
                if i > 0 and remains[i] == remains[i - 1]:
                    continue
                path.append(num)
                backtrack(remains[:i] + remains[i + 1:])
                path.pop()

        nums.sort()
        path: list[int] = []
        backtrack(nums)
        return result