[LeetCode/Python] 78. 부분 집합(Subsets)

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

 

Example:

 

Input: nums = [1,2,3]

 

Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

 

 

 

 

1. 내가 직접 푼 코드(itertools 짱짱맨)

 

 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
 
        for i in range(len(nums)+1):
            result += list(itertools.combinations(nums,i))
 
        return result

 

해설:

 

어떻게 풀지 고민하다가 itertools가 떠올랐다!

 

속도는 상위 5퍼센트 안에 들더라.

 

combinations( 수열 , 뽑을 개수 )를 넣어주면 된다.

 

 

 

 

 

 

 

** 깔끔한 답안 **

 

 

 

 

2. 트리의 모든 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

 

해설:

 

 

부분 집합 트리

 

다음 그림과 같이 코드를 짜면 된다!