DFS/BFS 타겟 넘버

DFS를 활용한 문제.

 

내가 풀지 못했다...

어떻게  이렇게 쉽게 잘 풀 수 있을까?

 

나는 DFS에 대해 정확히 이해하지 못하고 있었나보다.

자꾸 연산자(+,-)를 DFS로 넣을 생각만하고 숫자 자체로의 더하기 빼기에는 전혀 생각못했다.

이건 DFS를 정확히 이해하지 못하고 있기 때문인 것 같다.

DFS문제를 더 풀어보면서 정확한 이해가 뒷받침 되어야 할 것 같다.

 

#include <string>
#include <vector>

using namespace std;
int answer=0;

void dfs(vector<int> numbers, int target, int sum, int idx);


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

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