[LeetCode]Subsets

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

Subsets - LeetCode

 

문제 분석

주어진 숫자배열을 가지고 가능한 모든 부분집합을 구하는 문제입니다. 순서는 상관 없습니다.

 

처음 시도한 답안

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

        def dfs(answer, nums, path):
            answer.append(path[:])

            for idx, num in enumerate(nums):
                path.append(num)
                dfs(answer, nums[idx+1:], path)
                path.pop()

        dfs(answer, nums, [])

        return answer

접근 방법

1. dfs를 이용해 Subsets을 구합니다.
2. answer에 path를 기록합니다.
3. 파라미터로 전달받은 nums 요소를 순회합니다.
4. path에 num을 등록합니다.
5. dfs를 재귀적으로 실행합니다. nums의 요소는 idx+1로 슬라이싱 합니다.
6. path에 등록한 num을 제거합니다.

기본적인 DFS 알고리즘을 활용해 Subsets을 구할 수 있습니다. 탐색하는 경로는 다음과 같습니다.

# path 경로
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

따라서 이 경로들을 모두 answer에 넣어주면 됩니다.