프로그래머스 타겟넘버

문제

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

풀이

깊이우선탐색(DFS)를 이용하여 더하고 빼나가는 트리를 구성한다. 깊이가 배열의 크기만큼 됐을 때 모든 합계를 더하여 target과 일치한다면 answer의 값을 증가시키도록 했다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int depth)
{
	int sum = 0;
	if (depth == numbers.size())
	{
		for (int i = 0; i < numbers.size(); i++)
		{
			sum += numbers[i];
		}

		if ( target == sum )
		{
			answer++;
		}
	}
	else
	{
		numbers[depth] = +numbers[depth];
		dfs(numbers, target, depth + 1);
		numbers[depth] = -numbers[depth];
		dfs(numbers, target, depth + 1);
	}
	
}

int solution(vector<int> numbers, int target)
{
	dfs(numbers, target, 0);
	return answer;
}

int main()
{
	vector<int> number(5, 1);
	
	solution(number, 3);

	cout << answer;
}