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

LeetCode 문제 해석 및 풀이 방법

문제 78. Subsets(하위 집합)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given an integer array nums of unique elements, 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
• All the numbers of nums are unique.

 

입출력 예

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

 

해답 및 해설

파이썬 (Python)

재귀를 이용한 풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def helper(nums):
            if len(nums) == 0:
                return [[]]

            elem = nums.pop()
            last_subsets = helper(nums)

            return last_subsets + [subset + [elem] for subset in last_subsets]
        
        return helper(nums)

부분집합을 만드는 문제로, 위 풀이는 재귀를 이용하여 원소를 하나 뺐을 때의 부분집합을 불러온 다음, 거기 부분집합들에 뺀 원소들을 더해줘서 푼 풀이이다.

 

비트마스크를 이용한 풀이

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

        for mask in range(1<<len(nums)):
            subset = []
            idx = 0

            while mask:
                if mask & 1:
                    subset.append(nums[idx])
                mask >>= 1
                idx += 1
            
            result.append(subset)
            
        return result

 

 

https://programming4myself.tistory.com/96

🧮 부분 집합, 멱집합 구하기 알고리즘 직접 구현!

이전에 블로그에도 자세히 적어뒀으니 관심 있으신 분들은 한번 보면 좋을 것 같다.