60. 합이 같은 부분집합(DFS : 아마존 인터뷰)

it 취업을 위한 알고리즘 문제풀이

문제

코드

//60. 합이 같은 부분집합(DFS : 아마존 인터뷰)
#include <stdio.h>
#include <stdlib.h>
int n;
bool flag = 0;
int num[10];
int subnum[10];
int sum1;
int sum2;
//부분집합 구하기
void dfs(int level) {
    if (flag == true) return;
    if (level == n) {

        //부분집합 누적합 구하기
        sum1 = sum2 = 0;
        for (int i = 0; i < n; ++i) {
            if (subnum[i] == true) {
                sum1 += num[i];
            }
            else {
                sum2 += num[i];
            }
        }

        if (sum1 == sum2) {
            flag = 1;
        }
        return;
    }

    subnum[level] = true;
    dfs(level + 1);

    subnum[level] = false;
    dfs(level + 1);

}

int main() {
    //freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num[i]);
    }
    //부분집합 구하기
    dfs(0);

    if (flag == 1) {
        printf("YES\n");
        return 0;
    }

    printf("NO\n");
    return 0;
}

문제해결방법1

• 깊이 우선 탐색(DFS)로 해결 했다.
• 부분집합의 포함시킬 원소를 선택하면서 합을 누적해가고, 구한 합을 전체 원소의 합에서 빼서 나머지 다른부분 집합의 합을 구한다.
• 2진트리 형태의 깊이우선탐색으로 좌측에 있는 트리에는 현재 depth값과 같은 index의 요소를 부분집합에 포함시키도록 ture값을 주고 우측 트리에 있는 트리에는 현재 depth값과 같은 index의 요소를 부분집합에 포함시키도록 false값을 주면서 깊이우선탐색을 수행했다.
• depth가 집합의 주어진 원소의 개수 n에 도달하면 깊이우선탐색을 종료하면서 문제의 주어진 부분집합의 sum값을 구한다.
  • sum 값을 구하는 알고리즘은 true값을 준 인덱스의 요소의 값들을 누적하여 더하고 false값으로 남아있는 인덱스의 요소들을 누적해서 더하고 두 값을 비교하여 같다면 flag값을 true로하여 dfs함수 return이 끝났을 때 flag값이 true 이면 YES를 출력하도록 한다. 아니면 NO를 출력한다.
  • 이때 다음 dfs함수 호출에서 이미 flag값이 true라면 더 이상 계산할 필요가 없기 때문에 return하는 부분을 추가시켜 프로그램의 효율성을 증가시킨다.

문제해결방법1

• 입력받으면서 문제의 주어진 집합의 원소들의 total값을 구한다.
• 같은 방식이지만 sum 값을 같이 매개변수로 주어 depth마다 현재 depth값에 해당하는 index의 요소값을 누적하여 다음 dfs 함수의 sum매개변수에 전달하여 누적값을 구하는 코드도 구현하였다.
• 트리의 우측에서 현재 depth에 해당하는 index의 요소값을 포함시키고 싶지 않을 때는 그냥 현재 depth에서의 sum만 다음 함수의 sum매개변수에 전달하면 된다.
• 그리고 나머지 부분집합에 대해서는 집합전체의 합에서 현재 sum값을 total값에서 빼주어 나머지 부분집합의 합를 구한다.
• 이때 두 값이 같다면 위에서와 마찬가지고 flag값을 true로 하며 YES값을 출력하도록 하고 false라면 NO를 출력하도록 한다.