[DFS 개념정리] 특정 수 만들기 — ‘참여하지 않는 가지’를 직접 떠올린 순간

🔍문제

N개의 원소로 구성된 자연수 집합이 주어지면, 집합의 원소와 ‘+’, ‘-’ 연산을 사용하여 특정 수인 M을 만드는 경우가 몇 가지 있는지 출력하는 프로그램을 작성하세요. 각 원소는 연산에 한 번만 사용합니다.
예를 들어 {2, 4, 6, 8}이 입력되고, M=12이면 2+4+6=12 4+8=12 6+8-2=12 2-4+6+8=12 로 총 4가지의 경우가 있습니다. 만들어지는 경우가 존재하지 않으면 -1를 출력한다.

입력
첫 번째 줄에 자연수 N(1<=N<=10)와 M(1<=M<=100) 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

4 12 2 4 6 8

출력
첫 번째 줄에 가능한 집합의 개수를 출력한다.

4

🧠 내가 헷갈렸던 부분

처음에는 +, -만 두면 된다고 생각했는데,
일부 조합(예: 4+8=12)에서 원소가 참여하지 않는 것을 보고
“참여하지 않는 경우는 어떻게 하지?”라는 의문이 생김.

💡깨달은 점

“참여하지 않는다”는 것도 결국 한 가지 선택지다.
그래서 DFS에서 단순히 +, - 두 갈래가 아니라
세 갈래로 분기해야 모든 경우를 탐색할 수 있다.

✅ 코드 요약

void DFS(int L, int sum)
{
    if (L > n)
    {
        if (sum == m) Cnt++;
    }
    else
    {
        DFS(L + 1, sum + arrNum[L]); // +
        DFS(L + 1, sum - arrNum[L]); // -
        DFS(L + 1, sum);             // 참여하지 않음
    }
}

✨ 정리 한 줄
“DFS는 선택지를 모두 뻗는 트리 구조다.
포함하지 않는 것도 하나의 선택지다.”