61. 특정 수 만들기(DFS : MS 인터뷰) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>


int n, m, count = 0;
int a[11];
void DFS(int x, int sum)
{
	if(x == n+1)
	{
		if(sum == m)
			count++;
	}	
	else
	{
		DFS(x+1, sum+a[x]);
		DFS(x+1, sum-a[x]);
		DFS(x+1, sum);
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	DFS(1, 0);
	
	if(count == 0)
		printf("%d", -1);
	else
		printf("%d", count);
	return 0;
}

1. 원소의 개수 n, 특정한 수 m, 그 수가 나올 수 있는 경우의 수 count, 입력된 원소를 저장할 배열 a를 선언한다.

2. DFS에서는 세 가지 경우로 가지칠 수 있다.

- 원소를 덧셈에 이용할 때 (DFS(x+1, sum+a[x])

- 원소를 뺄셈에 이용할 때 (DFS(x+1, sum-a[x])

- 원소를 산술에 이용하지 않을 때 (DFS(x+1, sum))

3. sum == m 이라면 count++을 해준다.