合計部ダイバーシティ(DFS)
5092 ワード
完全なナビゲーション(遡及、ステータスツリー、エッジの切断)-深度優先ナビゲーションベース
に質問
合計(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
コード#コード#💻インフラストラクチャ:Pythonアルゴリズム回答
に質問
合計(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")
リファレンスReference
この問題について(合計部ダイバーシティ(DFS)), 我々は、より多くの情報をここで見つけました https://velog.io/@jsj3282/합이-같은-부분집합DFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol