알고리즘

[리트코드(LeetCode)] 78번 Subsets

욘아리 2024. 1. 11. 22:42

문제

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

 

Subsets - LeetCode

Can you solve this real interview question? 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: n

leetcode.com

모든 부분 집합을 반환하는 문제다.

예시

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]]

풀이

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        answers = []
        q = deque([(0, [])])

        while q:
            idx, cur = q.popleft()

            answers.append(cur[:])

            for i in range(idx, len(nums)):
                q.append((i + 1, cur  + [nums[i]]))

        return answers

 

- 너비 우선 탐색을 사용하여 부분 집합을 생성한다.