[LeetCode] 78. Subsets - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/subsets/

Subsets - LeetCode

유형 : 백트래킹(BackTracking)

문제 설명

중복되지 않는 숫자들이 담긴 배열 nums가 주어질 때, nums의 요소들로 만들 수 있는 모든 하위 집합을 return 하는 문제이다. 모든 하위 집합을 중복없이 임의의 순서로 return 하면 된다.

Example 1)
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2)
Input: nums = [0]
Output: [[],[0]]

제한사항

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums의 모든 숫자들은 unique하다.

문제 풀이

성공 코드

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.subsets = []
        
        self.bt(0, [])
        
        return self.subsets
    
    def bt(self, index: int, crnt_set: List[int]):
        if index == len(self.nums):
            self.subsets.append(crnt_set.copy())
            return

        num = self.nums[index]
        self.bt(index+1, crnt_set)

        crnt_set.append(num)
        self.bt(index+1, crnt_set)
        crnt_set.pop()

시간 복잡도 : O(n*2^n)

공간 복잡도 : O(n)