[LeetCode 해석 및 풀이] 90. Subsets II(하위 집합 II)

LeetCode 문제 해석 및 풀이 방법

문제 90. Subsets II(하위 집합 II)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

 

The solution set must not contain duplicate subsets. Return the solution in any order.

 

한글

중복을 포함할 수 있는 정수 배열 nums 주어지면 가능한 모든 하위 집합(멱집합) 을 반환합니다.

 

솔루션 세트에는 중복된 하위 세트가 포함되어서는 안 됩니다. 답은 어떤 순서로든 반환 가능합니다.

 

제한조건

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

 

입출력 예

입력	출력
nums = [1,2,2]	[[],[1],[1,2],[1,2,2],[2],[2,2]]
nums = [0]	[[],[0]]

 

해답 및 해설

파이썬 (Python)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        num_count = {}
        for num in nums:
            num_count[num] = num_count.get(num, 0) + 1

        def setHelper(num_count):
            if not num_count:
                return [[]]
            
            num, count = num_count.popitem()
            last_sets = setHelper(num_count)

            result = last_sets.copy()

            for i in range(1, count+1):
                result += [s + [num]*i for s in last_sets]

            return result
        
        return setHelper(num_count)

 

이전에 풀었던 하위 집합 I의 변형 버전 문제. 원소가 중복되어 몇 개씩 들어가있는지 세어준 다음, 해당 원소를 뺴고 구한 부분집합 리스트 원소들에 중복된 만큼 원소를 추가하는 방식을 이용하였다.