[Programmers/C++] 타겟 넘버

시간 복잡도

• 숫자의 개수가 최대 20개 이고 각 숫자가 양수, 음수의 경우의 수를 구해야 하므로 $O(2^20)$ 으로 약 1,000,000 입니다.

문제 접근법

• 모든 숫자에 대해 양수, 음수의 경우를 계산하며 합이 타겟과 같은지 DFS를 이용하여 구합니다.
• 모든 숫자에 대해 진행을 했고 타겟과 숫자의 합이 같으면 정답 개수를 증가시킵니다.

코드

#include <string>
#include <vector>

using namespace std;

static vector<int> visited;
static int answer=0;

void DFS(vector<int>& numbers, int sum ,int now, int size, int target)
{   
    if(now==size)
    {
        if(target==sum)
        {
            answer++;
        }        
        return;
    }
    
    DFS(numbers, sum+numbers[now], now+1, size, target);
    DFS(numbers, sum-numbers[now], now+1, size, target);
}


int solution(vector<int> numbers, int target) {
    
    int size = numbers.size();
    visited.resize(size);
    
    DFS(numbers, 0, 0, size, target);
    
    return answer;
}