Subsets

Subsets - LeetCode

접근 방법 [필수 작성]

제한조건 확인

• 최대 10! 의 연산 -> 특정 원소가 들어갈지 말지 결정 -> 2^10 (원소 갯수 최대 10개) -> 2^10 << 10^8 -> 완탐으로 풀이 가능
• 모든 원소 고유한 값이므로 중복 걱정 x

기본 재귀 구조인 아래 구조를 활용

a.append()
backtrack()
a.pop()

코드 구현 [필수 작성]

# 6시 40분 시작 -> 6시 45분 끝

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

        def backtrack(start, candidate):
            result.append(candidate[:])

            for i in range(start,len(nums)):
                candidate.append(nums[i])
                backtrack(i+1,candidate)
                candidate.pop()
            
        backtrack(0,[])

        return result

배우게 된 점 [ 필수 X ]

자유 형식

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

해당 문제의 시간복잡도는 O(2^n)이며 n 범위의 최대값인 10을 대입해도 10^8을 초과하지 않습니다. 이항 정리를 통한 모든 조합의 합을 계산하면 위 시간 복잡도를 유도할 수 있습니다.