[Python 알고리즘] 부분집합 (DFS)

1. 부분집합

1부터 N까지의 부분집합을 구할때 DFS로 부분집합을 구현할 수 있다.

집합 원소는 포함할 수, 포함하지 않을 수로 체크하는 배열을 두어서 구현한다.

DFS가 N+1까지 도달하면 포함하기로 한 수를 차례로 출력한다.

 

#부분집합
def dfs(v):
    if v==n+1: #도착점
        for i in range(1,n+1):
            if ch[i]==1: print(i, end=' ')
        print()

    else:
        ch[v]=1 #사용하겠다
        dfs(v+1)
        ch[v]=0 #사용안함
        dfs(v+1)


if __name__=="__main__":
    n=int(input())
    ch=[0]*(n+1)
    dfs(1)

실행결과

 

 

2. 합이 같은 부분집합 (응용)

입력받은 배열의 합과 부분집합의 합의 차이를 이용한다. (total-sum)

사용할 원소는 해당 원소를 더해준다.

사용하지 않을 원소는 기존 sum 값을 유지하고 트리 레벨만 증가시킨다.

 

import sys

def dfs(lev,sum): #tree level
    if sum>total//2: return #cut off (합이 같은 부분집합이므로 절반 이상 합산은 제거)

    if lev==n: #dfs탈출
        if sum==(total-sum):
            print("합이같은 부분집합 존재 : ",sum)
            sys.exit(0)

    else:
        dfs(lev+1, sum+arr[lev]) #사용
        dfs(lev+1, sum)          #사용x (기존 sum 그대로)

if __name__=="__main__":
    n=int(input())
    arr=list(map(int,input().split()))
    total=sum(arr)
    dfs(0,0)

    print("합이 같은 부분집합 없음") #dfs 함수에서 종료처리 안됐을 시

실행결과

[1,3,5,7] [6,10] 16으로 합이 같은 부분집합이 존재한다.

 

 

 

 

 

---

참고

파이썬 알고리즘 문제풀이 입문 (코딩테스트 대비) - 인프런 | 강의