[알고리즘][C++][DFS] 특정 수 만들기 (MicroSoft 인터뷰 문제)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

//	경로까지 출력하는 코드
int a[11], n, m, cnt = 0, path[10];
void DFS(int L, int sum) {
	if (L == n + 1) {
		if (sum == m) {
			cnt++;
			for (int i = 1; i < L; i++) {
				printf("%d ", path[i]);
			}
			puts("");
		}
	}
	else {
		path[L] = a[L];
		DFS(L + 1, sum + a[L]);
		path[L] = 0;
		DFS(L + 1, sum);
		path[L] = -a[L];
		DFS(L + 1, sum - a[L]);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	DFS(1, 0);
	if (cnt == 0) printf("-1\n");
	else printf("%d\n", cnt);
	return 0;
}

 

 

이 DFS 문제에서는 분기가 세가지로 나누어집니다. 

1. 더할 때
2. 뺄 때
3. 연산에 포함시키지 않을 때

이를 생각하면서 탈출 조건을 걸어주고, PATH 배열을 통해서 연산의 경로까지 출력시켜 보았습니다.