Python 알고리즘 인터뷰 - 문제 37. 부분 집합

leetcode78. - https://leetcode.com/problems/subsets/description/ 

 

모든 부분 집합을 리턴하라

 

예제

입력

nums = [1, 2, 3]

 

출력

[

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

[1, 2, 3],

[1, 3],

[2, 3],

[1, 2],

[]

]

 

풀이

조합의 모든 리스트를 저장하는 문제로 볼 수 있다. [1, 2, 3]의 경우 가능한 조합은 다음과 같다.

각 dfs 순회 중의 조합을 results에 추가하는 방식으로 코드를 구현한다. 

전체 코드는 다음과 같다.

def subsets(nums):
    results = []

    def dfs(start, elements):
        results.append(elements)
        for i in range(start, len(nums)):
            dfs(i + 1, elements + [nums[i]])

    dfs(0, [])

    return results