합이 같은 부분집합(DFS : 아마존 인터뷰) (1) 썸네일형 리스트형 [인프런 자바/java] 1. 합이 같은 부분집합(DFS : 아마존 인터뷰) _디버깅의 눈물 체크 포인트 1. DFS(깊이 우선 탐색)을 이용하는 문제 -두 부분집합의 합이 '같은 경우'가 존재하는 지 확인하는 문제 -해당 경우가 존재하는지 모두 탐색하기 위해 DFS 활용 2. 모집합의 총합이 홀수인 경우 체크 // 전체 원소의 합이 짝수인 경우에만 실행, if(sumLimit%2 == 0){ // 전체 합의 절반이 되어야 두 부분집합의 합이 동일할 수 있다. sumLimit = sumLimit/2; // DFS탐색 시작 DFS(0,0); } -모집합의 총합이 홀수인 경우, 두 부분집합의 합은 동일할 수가 없다. -부분집합은 2개만 존재하기 때문이다. -따라서 해당 경우의 수를 DFS 탐색 전에 처리했다. 3. '하나의 부분집합 원소의 총합'이 '전체 원소의 합/2인 경우'를 탐색 4. 두 가지.. 이전 1 다음