[리트코트-78] Subsets - Python

 

 

문제 소개

 

nums = [ 1 , 2 , 3 ] 이라는 집합의 모든 부분 집합을 리턴하라

출력 
[ [],[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3] ]

 

 

 

사용한 알고리즘

 

 

Path를 입력값으로 가지고가는 DFS

 

 

 

Code 

 

nums=[1,2,3]

result = []

def DFS(indx,path):
    result.append(path)

    for i in range(indx,len(nums)):
        DFS(i+1,path+[nums[i]])


DFS(0,[])
result





## 아래는 특별히 길이가 2개인 순열을 찾는 DFS이다 Path를 사용한 방식은 비슷하다.
result = []
def DFS1(n_len,path):

    if len(path)==n_len:
        result.append(path)
        return

    for i in range(1,len(nums)+1):
        if i not in path:
            DFS1(n_len,path+[i])

DFS1(2,[])

 

 

 

마무리

 

DFS탐색중에 지나온 Path를 DFS함수의 인자로 사용하여 Path를 기억하는 식이다.

 

※ end