(Python)[LeetCode] Subsets

문제

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• 10 <= nums[i] <= 10
• All the numbers of nums are unique.

문제풀이

소스코드

from typing import List

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

묶음을 만들어 나가야 하는 문제이므로 dfs를 사용해야 할 것 같다고 생각했다. path를 만들어 나가면서 인덱스를 1씩 증가하는 형태로 깊이 탐색한다.

예시