[C++] DFS - 합이 같은 부분집합(아마존 인터뷰)

#include <iostream>
#include <vector>

using namespace std;

int a[11];
int N,tot = 0;
bool flag = false;

void DFS(int L, int sum){//L이 곧 인덱스를 가리킴
    if(sum > (tot/2)) return;// 이전 으로
    if(flag == true) return; // 스택프레임 모조리 삭제
    if(L == N+1){
        if(sum == (tot-sum))
            flag = true;
    }
    else{
        DFS(L+1, sum+a[L]);
        DFS(L+1, sum);
    }
}

int main() {
    int i,tmp;
    
    scanf("%d",&N);
    
    for(i = 1; i <= N; i++){
        scanf("%d",&a[i]);
        tot += a[i];
        cout << tot;
    }
    
    DFS(1,0);
    
    if(flag) printf("YES");
    else printf("NO");
    return 0;
}

• 이 문제는 부분 집합들의 합에 대한 모든 경우의 수를 알아야 하므로 DFS로 풀이 가능한 문제이다.
• 문제를 읽어보면 집합을 두 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 같은지를 알아야 한다.
• 두 부분집합의 합이 같으려면 두 부분집합은 각각 (집합의 총합/2)만큼의 값을 가져야 한다.
• 1 3 5 6 7 10이라는 값이 주어졌다면 32/2 == 16만큼의 값을 가진 두 부분집합이어야 한다.
• 따라서, 만약, 재귀를 실행하던 도중에 16이라는 값을 지닌 두 부분집합이 발견되었다면 재귀를 더이상 하지 않아도 되므로 완전종료해야 한다.(flag를 이용한다.)
• 그리고 Tree의 레벨을 넘어서서 자식 노드를 생성해서는 안된다.
• 부분집합의 합에 대한 문제이므로, 각 함수는 자신의 값을 덧셈한다와 안한다 두 가지로 나누어 자식 노드를 생성해야한다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard