[파이썬 알고리즘] 25. 부분 집합

1. 문제

Leetcode 78. subsets

정수형 배열 nums가 주어지면, 부분 집합을 모두 리턴하여라.

 

2. 풀이

DFS를 이용해서 탐색을 진행한다. 먼저 중복되지 않는 부분집합을 만들기 위해서는 한번 고른 원소 뒤에 있는 원소만 고른다는 규칙을 설정해주어야 한다. 이를 확인하기 위해, index라는 변수에 지금까지 탐색한 원소 중 가장 뒤에 있는 원소의 index를 저장한다. 탐색은 index 이후의 원소에 대해서만 진행한다. 그리고 변수 path에는 현재 탐색 중인 부분집합을 저장한다. path에 index 이후의 원소를 하나씩 추가하고, 다시 dfs 함수를 호출하는 방식으로 탐색을 진행한다. 또한 모든 부분 집합을 리턴해야 함으로 dfs 함수가 실행될 때마다 path를 result에 추가하고, 탐색이 종료되면 result를 리턴한다.

 

3. 전체 코드

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

        def dfs(index, path):
            # 매 번 결과 추가
            result.append(path)

            # 경로를 만들면서 DFS
            for i in range(index, len(nums)):
                dfs(i + 1, path + [nums[i]])

        dfs(0, [])
        return result