[LeetCode 풀이/python] 47. Permutations II (medium)

문제 설명: 중복을 허용하는 숫자들의 집합 nums 가 주어졌을 때, 이를 통해 만들 수 있는 모든 고유한 순열(permutations) 조합을 리턴하시오. 리스트 내 조합의 순서는 무관하다.

 

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

 

예시 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

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 배열 nums 에 포함된 숫자에는 중복이 허용되나 결과적으로 순열 조합은 중복되면 안되어서 기본적인 백트래킹 알고리즘에 +@ 가 필요...!
  • 단순히 마지막에 기존 res 에 동일한 순열이 존재하지 않을 경우에만 경로를 추가하는 식으로 하면 중복되는 경로 탐색을 피할 수 없음 ㅜ
  • 일단 배열 nums 를 정렬한 뒤, 기준 숫자가 직전에 사용한 숫자와 동일한 경우 이전 탐색 결과와 중복되므로 스킵(continue)~

 

• 코드 구현

def permuteUnique(nums: List[int]) -> List[List[int]]:
    res = []
    nums.sort()
    max_len = len(nums)
    dfs(nums, max_len, [], res)
    return res
    
def dfs(nums, max_len, path, res):
    if (len(path) == max_len):
        res.append(path)
        return
    
    for i in range(len(nums)):
        if (i>0) and (nums[i] == nums[i-1]): continue
        dfs(nums[:i]+nums[i+1:], max_len, path+[nums[i]], res)

 

• 결과
  • 깔끔하고 효율적인 코드로 무난히 통과 ~_~
  • Discussion 을 둘러보니 Upvote 상위 솔루션 중에 동일한 접근법의 풀이가 있어서 뿌듯 ~_~