47. Permutations II

Description

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

Example 1:

• Input: nums = [1,1,2]
• Output: [[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

Submitted Code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(path):
            if len(path) == len(nums):          # 종료조건
                result.append(path.copy())
                return

            for i in range(len(nums)):
                if visited[i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and not visited[i-1]: # 같은 숫자면 바로 앞의 값 사용 여부 확인
                    continue

                visited[i] = True           # 선택
                path.append(nums[i])

                dfs(path)                   # 재귀호출

                visited[i] = False          # 복구
                path.pop()

        nums.sort()                             # [1, 1, 2]
        visited = [False] * len(nums)           # [False, False, False]
        result = []
        dfs([])

        return result

Runtime: 3 ms | Beats 90.70%
Memory: 19.88 MB | Beats 63.16%

nums를 오름차순 정렬 후 각 원소가 사용되었는지 체크하는 배열 visited를 하나 더 생성하는 방법이다. 동일 원소가 여러 개 있을 경우 가장 앞의 원소부터 순서대로 사용해야 같은 조합을 막을 수 있기 때문이다.

Other Solutions

1st

class Solution:
    def permuteUnique(self, nums):
        res = []

        def backtrack(i):
            if i == len(nums):
                res.append(nums[:])
                return

            seen = set()

            for j in range(i, len(nums)):
                if nums[j] in seen:
                    continue
                seen.add(nums[j])

                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i + 1)
                nums[i], nums[j] = nums[j], nums[i]  # backtrack

        backtrack(0)
        return res

time complexity: 𝑂(𝑛*𝑛!)
space complexity: 𝑂(𝑛)

두 원소를 swap하는 방법을 사용하기 위해 해시셋으로 중복을 제거한 코드도 참고했다.