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

 

▣ 입력예제 

 

4 12

2 4 6 8

 

 

▣ 출력예제 

 

4

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, a[11], cnt = 0;

void DFS(int L, int sum)
{
	if (L == n+1)
	{
		if (sum == m)
		{
			cnt++;
		}
	}
	else
	{
		DFS(L+1, sum + a[L]);
		DFS(L+1, sum);
		DFS(L+1, sum - a[L]);
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}

	DFS(1,0);

	if (cnt == 0)
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
		cout << cnt << endl;
	}
}