61. 특정 수 만들기(DFS : MS 인터뷰)

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

문제

코드

//61. 특정 수 만들기(DFS : MS 인터뷰)
#include <stdio.h>
int n, m, cnt;
int num[10];


void dfs(int depth, int total) {
    if (depth == n) {
        if (total == m)
            ++cnt;
        return;
    }

    dfs(depth + 1, total + num[depth]);
    dfs(depth + 1, total - num[depth]);
    dfs(depth + 1, 0 + total);

}
int main() {
    //freopen("input.txt", "rt", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num[i]);
    }

    dfs(0, 0);
    if (cnt == 0) {
        printf("%d", -1);
    }
    else
        printf("%d", cnt);

    return 0;
}

문제해결방법

• DFS로 문제를 해결했다.
• depth별로 문제에 주어진 인덱스에 해당하는 요소를 +요소,-요소,0(해당 요소값 포함하지 않음 의미)으로 합을 구해 depth가 n이 될때 까지깊이우선 탐색을 진행하고 합이 m이 될때 카운트 값을 증가시키도록 코드를 구현했다.