algorithm/leetcode

Subsets [leetcode]

hoonzii 2022. 2. 13. 17:16
반응형

문제 

 

Subsets - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

문제풀이

문제 예시로 나온 답을 보고 풀게 되었다.

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

규칙이 보이는가?

output 에 처음에는 [] (빈 리스트) 공집합 하나만 추가해준다.

 

num = 1 일때,

output 을 순회하면서 이전 집합에 1을 추가한다. (temp_list = [] + 1 = [1])

output에 추가해준다 ⇒ output = [ [], [1] ]

 

num = 2 일때,

output 을 순회하면서 이전 집합에 2를 추가해준다.

  1. [] + 2 = [2]
  2. [1] + 2 = [1,2]

output 에 추가해준다 ⇒ output = [ [], [1], [2], [1,2] ]

 

num = 3일때,

output을 순회하면서 이전 집합에 3을 추가해준다. 

  1. [] + 3 = [3]
  2. [1] + 3 = [1,3]
  3. [2] + 3 = [2,3]
  4. [1,2] + 3 = [1,2,3]

output 에 추가해준다 ⇒ output = [ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]

 

결과는

 

코드

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = []
        result.append(list())
        for i in range(len(nums)):
            num = nums[i]
            temp_result = []
            for subSet in result:
                temp_set = list(subSet)
                temp_set.append(num)
                temp_result.append(temp_set)
            result.extend(temp_result)
            
        return result

 

반응형