[2023년 11월 22일]타겟 넘버(9분)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

구현 아이디어 1분 구현 8분

풀이

재귀 넘길 때 sum을 넘기게 바꿀 예정.

#include <string>
#include <vector>

// +, - 로 구성된 배열을 만들면 된다.
int check[20], result;

using namespace std;

void DFS(int L, int e, const vector<int>& numbers, int target)
{
    if(L == e)
    {
        int sum = 0;
        for(int i = 0; i < e; ++i)
            sum += (numbers[i] * check[i]);
        
        if(target == sum) ++result;
    }
    else
    {
        check[L] = 1;
        DFS(L + 1, e, numbers, target);
        check[L] = -1;
        DFS(L + 1, e, numbers, target);
    }
}

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

풀이

#include <string>
#include <vector>

// +, - 로 구성된 배열을 만들면 된다.
int check[20], result;

using namespace std;

void DFS(int L, int e, int sum, const vector<int>& numbers, int target)
{
    if(L == e)
    {
        if(target == sum) ++result;
    }
    else
    {
        DFS(L + 1, e, sum + numbers[L], numbers, target);
        DFS(L + 1, e, sum - numbers[L], numbers, target);
    }
}

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