leetCode - Subsets

leetcode.com/problems/subsets/

 

1. 시간 복잡도 높은 풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        def DFS(level, node, subset):
            subset.append(node)
            if level == len(nums):
                subsets.append([num for num in subset if num != None])
                subset.pop()
                return
            for child in [None, nums[level - 1]]:
                DFS(level + 1, child, subset)
            subset.pop()
            
        subsets = []
        
        DFS(0, None, [])
        
        return subsets

 

수학에서 부분집합의 갯수가 2^n인걸 증명하는 과정과 똑같이 가지를 만들었는데, 다소 비효율적이다. 항상 DFS의 리프에서만 기록한다는 생각을 버리자.

 

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        def DFS(idx, subset):
            subset.append(nums[idx])
            subsets.append(subset[:])
            if idx != (len(nums) - 1):
                for next_idx in range(idx + 1, len(nums)):
                    DFS(next_idx, subset)
            subset.pop()
            
        subsets = [[]]
        
        for i in range(len(nums)):
            subset = []
            DFS(i, subset)
        
        return subsets

 

이와 같이

 1       2      3

 |\      |

2 3    3

|

3

의 트리로 모든 노드를 방문할때마다 기록하는 것이 더 효율적이다.