🌞문제

🌞접근법

조건1. n개의 음이 아닌 정수가 나열되어 있다.
조건2. 이들을 더하거나 빼서 target 넘버를 만들어야 한다.
조건3. 순서를 바꿀 수는 없다.
조건4. 주어지는 숫자의 개수는 2개~20개
조건5. 각 숫자는 1~50의 숫자
조건6. 타겟 넘버는 1~100의 숫자

결과값 : 더하거나 빼서 타겟넘버를 만드는 모든 방법의 수를 구하라

모든 경우를 탐색해도 될 것이라고 생각이 든다.
일단은 n의 숫자가 20개밖에 되지 않기 때문에 각 요소에 대해서 +, -의 경우를 모두 구하여 target인 경우에는
count라는 변수를 두어 값을 하나 추가하면 될 것이라고 생각이 든다.

모든 경우에 대해서 구하기 위해서는 dfs를 사용하는 편이 좋을 것 같다.
첫번째 요소가 +인 경우와 -인 경우 두개의 dfs를 만들어서,
다음 요소를 자식으로 갖게끔 하면 될 것으로 보인다. 다음 요소는 +와 -를 달고 자식이 된다.

🌞풀이

#include <string>
#include <vector>

using namespace std;

int count = 0;
int target;
vector<int> numbers;

void dfs(int idx, int cur_value)
{
    if(idx == numbers.size()-1)
    {
        if(target == cur_value) count++;
        return;
    }
    
    else
    {
        idx++;
        dfs(idx, cur_value+numbers[idx]);
        dfs(idx,cur_value-numbers[idx]);
    }

}



int solution(vector<int> _numbers, int _target) {
    numbers = _numbers;
    target = _target;
    dfs(0,numbers[0]);
    dfs(0,-numbers[0]);
    int answer = count;
    return answer;
}