37. Subsets

리트코드

• 모든 부분 집합을 리턴하라.

1. 트리의 모든 DFS 결과

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

• 이 문제는 트리를 구성하고, 트리를 DFS하는 문제로 풀이할 수 있다.

• 입력값이 [1,2,3] 일 때 다음과 같이 간단한 트리를 구성할 수 있다.

  • 이를 DFS하여 원하는 결과를 출력할 수 있다.

    

• DFS 코드를 구현해보자.

  • 경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태로 깊이 탐색한다.

  • 별도의 종료 조건 없이 탐색이 끝나면 저절로 함수가 종료되게 한다.

  • 부분 집합은 모든 탐색의 경로가 결국 정답이 되므로, 다음과 같이 탐색할 때마다 매번 결과를 추가하면 된다.