60. 합이 같은 부분집합[DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

6

 

출력예제 1

1 3 5 6 7 10

 

풀이 

- 하나의 DFS함수에는 (L+1, sum+a[L])으로 배열이 값을 더하고, 다른 하나는 (L+1, sum)으로 더하지 않고 간다

- L==n+1이 됬을 때 sum과 total-sum이 같으면 두 부분집합의 합이 같은 것이기 때문에 flag = true로 한다

- sum이 total/2보다 크다면 두 부분집합의 합이 같을 수 없으므로 return 시킨다

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, a[11], total;
bool flag=false;

void DFS(int L, int sum){
    if(sum>(total/2)) return;
    if(flag==true) return;
    if(L==n+1){
        if(sum==(total-sum)){
            flag=true;
        }
    }else{
        DFS(L+1, sum+a[L]);
        DFS(L+1, sum);
    }
}

int main(){
    int i;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        scanf("%d", &a[i]);
        total+=a[i]; //전체 합
    }
    DFS(1, 0);
    if(flag) printf("YES\n");
    else printf("NO\n");
    return 0;
}