[LeetCode | Python] 78. Subsets

unique element로 구성된 nums 배열이 주어졌을 때,

가능한 모든 subsets(부분집합)을 리턴하는 문제다.

 

 

접근 - 백트래킹

모든 부분 집합을 구하는 문제 -> 완전 탐색

반복문 vs 재귀 -> 반복문으로 모든 경우를 탐색하기 어려우므로 재귀(DFS)를 이용한 탐색,

nums의 각 원소를 포함할지 안 할지 선택 필요 -> 백트래킹

백트래킹은 모든 가능한 경우를 탐색하면서, 불가능한 경로는 빠르게 되돌아가(백트랙) 탐색을 줄이는 기법이다.
일반적으로 재귀(Recursion)을 이용한다.

 

부분집합 문제에서는  nums[i]를 선택할지 안 할지 결정하는 2가지 선택이 계속해서 분기되기에 백트래킹에 적합하다.

 

 

풀이: 백트래킹

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []

        def dfs(i):
            if i == len(nums):
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i+1)
            subset.pop()
            dfs(i+1)
        
        dfs(0)
        return res

모든 원소를 포함하는 경우 / 포함하지 않는 경우를 고려하므로 2^n개의 부분집합이 생성된다. 

기본적인 경우의 수 계산에서 O(2^n)이며,

각 부분 집합을 저장할 때 subset.copy()가 실행되므로 추가적인 O(n) 연산이 필요하다.

따라서 최종 시간 복잡도는 O(n * 2^n)이다.