하나둘셋넷

합이 같은 부분집합

 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

입력

 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

출력

 첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

입력 예시

 1 6 1 3 5 6 7 10

출력 예시
 YES

코드로 구현해보자

import sys
sys.stdin = open('.\DFS, BFS\인프런_알고리즘_강의\부분집합\합이 같은 부분 집합.txt','r')

def DFS(L, sum):
    if sum > total//2:
        return # 호출된 재귀함수를 종료하고 싶을 때는 return을 사용한다.

    if L == n:
        if sum ==(total-sum):
            print("YES")
            sys.exit(0)
    else:
        DFS(L+1, sum+a[L])
        DFS(L+1, sum)

n = int(input()) # 성분의 개수를 입력하자
a = list(map( int, input().split() )) # 안에 있는 요소들을 출력하자.
total = sum(a)
DFS(0, 0) # 여기에서 앞에 0은 시작 지점, 뒤는 현재까지의 누적합을 의미한다

.

부분집합_구하기

[문제]

첫 번째 줄부터 각 줄에 하나씩 출력예제 1과 같이 출력하려 한다. 출력 순서는 깊이 우선탐색 전위순회방식으로 출력한다. 단, 공집합은 출력하지 않는다.

[입력예제_1]

3

[출력예제_1]

1 2 3

1 2

1 3

1

2 3

2

3

import sys

sys.stdin = open("input.txt", "r") # txt에는 3이 입력되어 있다.



def DFS(v):

    if v == n+1: # 3까지 확인하는게 목표이므로 값이 4가 되었다면 현재까지 체크한 내용을 출력하도록 하자

        for i in range(n+1):

            if ch[i] == 1

                print(i, end = ' ')

            print()

    else:

        ch[v] = 1

        DFS(v+1)

        ch[v] = 0

        DFS(v+1)



n = int(input()) # 어디까지의 부분 집합을 구하고 싶은지 입력한다.

ch = [0] * (n+1)

DFS(1) # 1부터 체크를 시작한다.