[ 백준 1182 ] 부분 집합의 합 (C++)

백준의 부분집합의 합(1182) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 주어진 집합에서 입력으로 주어지는 특정 결과값을 도출해 낼 수 있는 부분집합이 몇 개인지 출력하는 문제이다.

   재귀를 통한 완전탐색을 이용해서 풀었다.

   재귀함수는 DFS(int Idx, int Sum, int Size) 이렇게 3개의 매개변수를 관리해 주었는데,

   Idx는 현재 Index번호를, Sum은 지금까지의 총합을, Size는 공집합인지 아닌지를 체크해주기 위해서, 사용된 매개변수이다.

   재귀를 호출하는 경우는 2가지 경우가 있다.

   현재 Idx의 값을 부분집합으로 합치는 경우와, 현재 Idx의 값을 부분집합으로 사용하지 않고 다음 Idx로 넘어가는 경우

   이 2가지에 대해서만 재귀호출을 해주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Dest, Answer;
int Arr[MAX];
 
void Input()
{
    cin >> N >> Dest;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void DFS(int Idx, int Sum, int Size)
{
    if (Idx == N)
    {
        if (Sum == Dest && Size != 0)
        {
            Answer++;
        }
        return;
    }
 
    DFS(Idx + 1, Sum + Arr[Idx], Size + 1);
    DFS(Idx + 1, Sum, Size);
}    
 
void Solution()
{
    DFS(0, 0, 0);
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}