61. 특정 수 만들기 (MS 인터뷰 문제 : DFS 완전탐색)

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int ar[11]; 
int br[11];
int num;
int target;
int cnt = 0;

void DFS2(int maxLevel, int curLevel, int* brr) {
	int* b = new int[maxLevel];

	for (int i = 0; i < maxLevel; i++)
		b[i] = brr[i];

	if (curLevel > maxLevel) {
		int res = 0;

		for (int i = 0; i < maxLevel; i++) {
			if (b[i] == 1) {
				res += br[i];
			}
			else {
				res -= br[i];
			}
		}

		if (res == target) cnt++;
	}
	else {
		b[curLevel - 1] = 1;
		DFS2(maxLevel, curLevel + 1, b);
		b[curLevel - 1] = 0;
		DFS2(maxLevel, curLevel + 1, b);
	}

	delete[] b;
}

void DFS(int maxLevel, int curLevel, int* arr) {
	int* a = new int[maxLevel]; 
	int sum = 0;
	int num = 0;
	for (int i = 0; i < maxLevel; i++) {
		a[i] = arr[i];
	}
	if (curLevel > maxLevel)
	{
		int count = 0;
		for (int i = 0; i < maxLevel; i++) {
			
			if (a[i] == 1) {
				num++;
				br[count++] = ar[i];
			}
		}

		int* brr = new int[num];
		for (int i = 0; i < num; i++)
			brr[i] = 1;
		DFS2(num, 1, brr);

		delete[] brr;
	}
	else {
		a[curLevel - 1] = 1;
		DFS(maxLevel, curLevel + 1, a);
		a[curLevel - 1] = 0;
		DFS(maxLevel, curLevel + 1, a);
	}
	delete[] a;
}

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	scanf("%d %d", &num, &target);
	int* arr = new int[num]; // 1 1 1 1

	for (int i = 0; i < num; i++) {
		arr[i] = 1;
	}

	for (int i = 0; i < num; i++) {
		scanf("%d", &ar[i]);
	}

	DFS(num, 1, arr);

	printf("%d", (cnt == 0) ? -1 : cnt);

	delete[] arr;
}

// 4 12 2 4 6 8