재귀함수로 부분집합의 합이 같은지 알아보기

✏️ 목표

하나의 집합을 두 개의 부분집합으로 나눌 때 두 부분집합의 원소의 합이 서로 같은 경우가 있으면 "Yes"를, 그렇지 않으면 "No"을 출력하는 프로그램을 작성해 보자.

 

 

 

💡 해결하기

➡️ 부분집합이 될 수 있는 모든 경우의 수를 하나씩 살펴보면서 해당 부분집합의 합과 나머지 부분집합의 합이 같은지를 각 케이스마다 비교하여 같은 경우 Yes를 출력하고 종료한다.

 

➡️ 모든 경우의 수를 살펴 보았는데도 합이 같은 경우가 존재하지 않는 경우 No을 출력하고 종료한다.

 

➡️ 이때 두 개의 부분집합의 합을 일일이 비교하는 것은 시간이 매우 오래 걸리므로 전체 원소의 합에서 현재 부분집합의 합을 뺀 것(나머지 원소로 이루어진 부분집합)이 현재 부분집합의 합과 같은지를 확인하는 방식으로 코드를 짜는 것이 좋다.

(전체 원소의 합은 시작할 때 미리 구하고 시작한다.)

 

➡️ 또한, 현재 구하고 있는 부분집합의 합이 전체 원소의 합의 절반을 넘어가면 나머지 부분집합이 현재 구하고 있는 부분집합과 합이 같을 가능성이 없으므로 현재 부분집합 구하기를 종료하고 다음 부분집합 구하기로 넘어가야 한다.

 

 

 

❓ 예제 분석해보기

* 참고

재귀 함수로 부분집합 구해보기 (tistory.com)

재귀 함수로 부분집합 구해보기

 

문제에서 입력으로 주어진 {1, 3, 5, 6, 7, 10}의 집합을 가지고 그려보겠다.

 

 

위와 같은 흐름으로 진행되다가 i가 elements의 마지막 요소의 인덱스인 5가 되면 종료된다.

중간에 [1, 3, 5, 6, 7] 과 같이 전체 원소의 합의 절반보다 큰 집합이 생성되면 더 이상 나아가기를 멈추고 해당 부분집합 만들기를 멈춘다.

완성된 부분집합이 [1, 3, 5, 7] 이면 합이 16이고, 나머지 원소들의 합은 전체 원소의 합 - 현재 부분집합의 합 = 32 - 16 = 16 으로 합 같다. 옆의 경우와 같이 합이 같아지는 경우 Yes를 출력하고 프로그램을 종료한다.

만약 완성된 부분집합이 [1, 3, 5] 같이 합이 전체 원소의 합 - 현재 부분집합의 합 의 계산 결과와 일치하지 않는다면 (더 작다면) 다음 부분집합 구하기로 넘어간다.

 

 

 

💻 Python으로 코드 작성하기

 

def DFS(i, _sum):     # elements에서 사용할 인덱스와 포함할 원소를 누적할 _sum이 인자로 들어감
    if _sum > total_sum // 2:     # 현재까지 포함된 원소들의 합이 모든 원소의 합의 절반보다 클 경우
        return     # 과정 종료
    elif i == n:     # 모든 원소들을 다 돌고,
        if _sum == (total_sum - _sum):     # 뽑은 원소들의 합이 나머지 원소들의 합과 같은 경우
            print("Yes")     # Yes 출력 후
            exit()     # 프로그램 자체를 종료
    else:
        DFS(i + 1, _sum + elements[i])     # 현재 i번째 원소를 포함하는 경우 
        DFS(i + 1, _sum)     # 현재 i번째 원소를 포함하지 않는 경우

n = int(input())     # 집합의 원소의 개수
elements = list(map(int, input().split()))     # 집합을 이루는 원소들
total_sum = sum(elements)     # 전체 원소의 합
DFS(0, 0)     # 인덱스는 0부터 하나씩 증가, 원소의 합도 0으로 초기화
print("No")     # 위 DFS 함수에서 프로그램 종료(exit())가 이루어지지 않은 경우 실행됨

 

종료 조건은 해결하기에서 작성한 대로 적어주었다.

종료 조건에 해당하지 않는 경우에는 DFS 함수를 재귀 호출해 주었는데, 현재 i번째 원소를 포함하는 경우와 현재 i번째 원소를 포함하지 않는 경우를 둘 다 처리해 주기 위해 2번 재귀 호출을 해 주었다.

 

 

 

📌 참고 강의

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 대시보드 - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의