[리트코드] Subsets(python)

리트코드, Subsets_부분집합

TL;DR

• 깊이 우선 탐색(DFS)

문제

1. 주어진 중복이 없는 정수 배열 nums에 대해서 생성할 수 있는 모든 부분 집합을 반환하라.
2. 정답 배열은 복사된 부분 집합을 포함해서는 안되며 정렬 순서에는 큰 상관이 없다.

입출력 형태

입출력 예시

 

- 주어진 숫자 배열로 만들 수 있는 모든 부분 집합을 반환하면 된다.

- 공집합 또한 부분 집합의 일부이므로 포함시켜야 한다.

풀이

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

 

- 이전까지의 문제들은 특정 조건을 만족했을 때만 정답 배열에 포함시키고(예 : 주어진 입력의 길이와 같을 때) 그렇지 않은 경우에는 포함시키지 않았었다. 하지만 이번 문제는 부분 집합을 구하는 문제이므로 특정 조건이 존재하지 않는다.

- 재귀 방식의 DFS를 구현하였다. 이 함수에서는 방문한 nums의 원소의 인덱스를 나타내는 index와 부분집합을 나타내는 subsets를 매개변수로 받는다.

  - dfs가 실행될 때, 우선 정답 배열에 생성된 subsets를 넣는다.

  - 그리고 방문한 인덱스 다음 인덱스를 방문하며 부분집합을 계속 만든다.