[파이썬 알고리즘] 78.leetcode - 부분집합

https://leetcode.com/problems/subsets/

Subsets - LeetCode

입력값이 [1,2,3]일 때 그림과 같은 간단한 트리를 구성한다면 이를 DFS하여 원하는 결과를 출력 할 수 있다.

def dfs(index, path):
    ...
    for in range(index, len(nums)):
        dfs(i + 1, path + [nums[i]])

경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태로 깊이 탐색을 한다. 별도의 종료 조건 없이 탐색이 끝나면 저절로함수가 종료되게 한다.

from typing import List


def subsets(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