[파이썬] 리트코드 78. Subsets 풀이

Subsets - LeetCode

nums = [1,2,3]일 때 부분집합의 개수를 구하는 문제다. 

탐색 알고리즘을 실행했을  때, 모든 탐색의 결과가 정답이 된다. 따라서 dfs로 간단하게 풀 수 있다.

 

1. 인덱스와 경로를 변수로 가지는 dfs를 정의하고 

2. 지나온 경로를 결과값에 저장하면서 

3. 모든 경로에 대해 탐색을 실행한다

 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [] 
        def dfs(index,path):
            result.append(path)
            for i in range(index,len(nums)):
                dfs(i+1,path+[nums[i]])
        dfs(0,[])
        return result