[파이썬 알고리즘 인터뷰][그래프] 부분 집합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

모든 부분 집합 리턴

 

책에서 구현된 코드

def subsets(self, nums: list[int]) -> list[list[int]]:
    result = []

    def dfs(index, path):
        result.append(path)
        
        for i in range(index,len(nums)):
        	dfs(i+1, path + [nums[i]])

    dfs(0, [])
    return result

 

기억해야할 기법

• 조건 확인해서 필요없는 코드 제거하기

 

내가 구현한 코드

def subsets(nums: list[int]) -> list[list[int]]:
    result = []

    def dfs(elts: list, s: int):
        result.append(elts)

        if len(elts) < len(nums):
            for i in range(s,len(nums)):
                dfs(elts + [nums[i]], i+1)

    dfs([], 0)
    return result

• for문의 range로 인해 if문이 필요가 없었다