프로그래머스 2단계 - 타켓넘버

https://programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 

코딩테스트 연습 - 타겟 넘버

- 문제파악

정수 배열과 타겟 넘버가 주어진다. 정수의 배열을 적절히 더하거나 빼서 타겟넘버를 만들 수 있는 경우의 수를 구하여라

 

- 정답

BFS/DFS 로 구분되어 있긴한데 굳이 그렇게 안풀고 그냥 재귀함수로 풀었다.

시간복잡도도 엄청 여유로운편..

 

#include <string>
#include <vector>

using namespace std;

vector<int> vec;
int answer;
int t;

void func(int k, int sum)
{
    if(k == vec.size())
    {
        if(sum == t)
            answer++;
                       
        return;
    }
        
    
    func(k+1,sum+vec[k]);
    func(k+1,sum-vec[k]);
}

int solution(vector<int> numbers, int target) {
    
    vec = numbers;
    t = target;
    
    func(0,0);
    
    return answer;
}