8-5) 합이 같은 부분집합(DFS: 아마존 인터뷰)
문제
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면
“YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
[입력설명]
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며, 그 크기는 1,000,000 이하입니다.
[출력설명]
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.
입력예제 1
6
1 3 5 6 7 10
출력예제 1
YES
문제풀이
코드
- 만약, {1, 5, 6}(합 12)을 선택했다면, 나머지의 합은
전체합(32)-12=20이다. 이 logic을 사용해서 문제를 쉽게 풀 수 있다. - 전체 코드의 원리는 다음 그림과 같다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(arr){
let answer="NO", flag=0;
let total=arr.reduce((a, b)=>a+b, 0);
let n=arr.length;
function DFS(L, sum){
//함수를 종료하는 기준
if(flag) return; //flag=1(답 발견한 것이 있을 때) 함수 종료(답발견한 이후에는 재귀 반복할 의미 없음)
//판단
if(L===n){
if((total-sum)===sum){
answer="YES";
flag=1; //answer="YES"(답을 발견했을 때)
}
}
else{
DFS(L+1, sum+arr[L]); //포함했을 때
DFS(L+1, sum); //포함하지 않았을 때
}
}
DFS(0, 0);
return answer;
}
let arr=[1, 3, 5, 6, 7, 10];
console.log(solution(arr));
</script>
</body>
</html>Author And Source
이 문제에 관하여(8-5) 합이 같은 부분집합(DFS: 아마존 인터뷰)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rladpwl0512/8-5-합이-같은-부분집합DFS-아마존-인터뷰저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
