[LeetCode] #78. Subsets (python)

문제

https://leetcode.com/problems/subsets/

Subsets - LeetCode

모든 부분집합을 반환해야 한다.

 

예시 입출력

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

 

풀이

 

내 풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
    
        output=[]
        
        def dfs(index, path):
            
            output.append(path[:])
            
            for i in range(index, len(nums)):
                path.append(nums[i])
                dfs(i+1, path)
                path.pop()
            
        
        
        dfs(0,[])
        
        return output

함수 종료 조건을 뭐로 잡을지 고민했는데 생각해보니까 굳이 종료 조건이 필요없었다. 모든 탐색 결과가 필요한 것이기 때문에 그냥 dfs 함수를 시작하면 다 최종 결과에 넣었다.

앞에서 부터 순서대로 탐색하기 위해서 dfs 인자로 index, 탐색 경로를 저장하기 위한 path를 사용했다. 반복문 시작값을 index로 해서 이미 탐색한 값은 제외했다. 탐색 후에는 path를 비우기 위해 pop을 사용했다.

 

책 풀이

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

        def dfs(index, path):
            # 매 번 결과 추가
            result.append(path)

            # 경로를 만들면서 DFS
            for i in range(index, len(nums)):
                dfs(i + 1, path + [nums[i]])

        dfs(0, [])
        return result

책에서도 나와 같은 풀이를 했는데 인자를 넘길 때 path+값으로 해서 나처럼 pop을 사용하지 않았다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰