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씩 증가하는 형태로 깊이 탐색한다.
-
별도의 종료 조건 없이 탐색이 끝나면 저절로 함수가 종료되게 한다.
-
부분 집합은 모든 탐색의 경로가 결국 정답이 되므로, 다음과 같이 탐색할 때마다 매번 결과를 추가하면 된다.
-
Author And Source
이 문제에 관하여(37. Subsets), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/37.-Subsets저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)