合計部ダイバーシティ(DFS)


完全なナビゲーション(遡及、ステータスツリー、エッジの切断)-深度優先ナビゲーションベース
に質問
合計(DFS:Amazonインタビュー)
N個の要素からなる自然数の集合が与えられた場合、その集合を2つの部分集合に分割した場合、2つの部分集合の要素の和が同じである場合は、「YES」を書き、そうでない場合は「NO」を書くプログラム.
2つの部分セットは2つの部分に分けられ、この2つの部分セットの合計は入力された元のセットになります.
例えば、{1,3,5,6,7,10}を入力すると、{1,3,5,7}={6,10}の2つの部分の集合の和が16に等しい場合があることを示す.
■説明の入力
第1行は自然数N(1<=N<=10)を与える.
2行目には、集合の要素N個が与えられる.各要素は重複しません.
■出力説明
1行目に「YES」または「NO」を出力します.
■入力例1
6
1 3 5 6 7 10
■出力例1
YES
コード#コード#💻
'''
상태 트리

왼쪽 자식으로 가면 자신을 부분집합에 넣는다.
오른쪽 자식으로 가면 자신을 인덱스를 부분집합에 넣지 않는다.

- 두개의 부분집합으로 나누었을때 각각의 합이 같은 경우 YES
- 한 부분집합에 어떤 값들이 들어가 있으면 
  다른 부분집합 중 어떤 부분집합에는 그 값들이 모두 포함이 안되고  
  들어가지 않았던 값들만 포함될 수 있다. (두 부분집합은 서로소 집합)
- 두 부분집합의 합이 홀수이면 YES가 나올 수 없음(2로 나눌 수 없기 때문)
- 부분집합의 sum들을 누적하다가 total // 2가 넘어가면 더이상 볼 필요가 없다.
'''

import sys
#sys.stdin=open("input.txt", "rt")  # read text

def DFS(L, sum):    # a 리스트의 인덱스 번호(Level), 부분집합의 합
    if sum > total//2:
        return
    if L == n:
        if sum == (total - sum):  # 두개의 부분집합으로 나누었을때 각각의 합이 같은 경우
            print("YES")
            sys.exit(0)           # 함수가 아닌 프로그램 종료
    else:
        DFS(L+1, sum+a[L])    # 부분집합에 자기자신 포함
        DFS(L+1, sum)         # 부분집합에 자기자신 미포함

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    total = sum(a)
    DFS(0, 0)
    print("NO")
リファレンス
  • インフラストラクチャ:Pythonアルゴリズム回答