[리트코드] 78. 부분 집합 (Python)

Subsets - LeetCode

문제

nums = [1,2,3]일 때 부분집합의 개수를 구해라

과정

• idx와 lst를 받는 dfs함수를 정의한다.
• 확인한 결과를 result에 저장해준다.

 

입력

[1,2,3]

출력

[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

 

풀이

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

        def dfs(idx, arr):
            result.append(arr)

            for i in range(idx, len(nums)):
                dfs(i+1, arr + [nums[i]])

        dfs(0, [])

        return result

 

한 줄씩 코드 해석해보기

result = []

• 결과를 반환할 result 리스트를 생성한다.

def dfs(idx, arr):
    result.append(arr)

• idx와 lst를 받는 dfs함수를 정의한다.
• lst 리스트를 result에 추가한다.
• ex) 처음 들어 온 값 [] 추가

    for i in range(idx, len(nums)):
        dfs(i+1, arr + [nums[i]])

• idx부터 nums의 길이까지 for문을 돌린다
• dfs에 idx값에는 i+1을 lst에는 [nums[i]]를 더해준 값을 넣는다.
• ex) 0 , [] 가 들어오고 dfs에 1 , [1] 이 들어가게 됨 

dfs(0, [])

return result

• dfs 초기 값에는 0과 []를 넣는다.
• result 반환

 

itertools를 이용한 풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        for i in range(len(nums)+1):
            result += list(map(list, itertools.combinations(nums, i)))
        return result