[깊이/너비 우선 탐색(DFS/BFS)] 타겟 넘버 C++

- PASS

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cnt;
int T;
int S;

void dfs(int le, vector<int> numbers, int sum) {
    if (le == S) {
        if (sum == T)
            cnt++;
        return;
    }
    
    dfs(le + 1, numbers, sum + numbers[le] );
    dfs(le + 1, numbers, sum - numbers[le] );
        
}


int solution(vector<int> numbers, int target) {
    int answer = 0;

    cnt = 0;
    T = target;
    S = numbers.size();
    dfs(0, numbers, 0);

    answer = cnt;
    return answer;
}

 

- TC1,2 시간초과 75.0/100

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cnt;
int T;
int S;

void dfs(int le, int st, vector<int> numbers, int sum) {
    if (le == S) {
        if (sum == T)
            cnt++;
        return;
    }

    for (int i = st; i < S; i++) {
        for (int j = 0; j < 2; j++){
            if(j==0)
                dfs(le + 1, i + 1, numbers, sum + numbers[i] );
            else
                dfs(le + 1, i + 1, numbers, sum - numbers[i] );
        }
    }
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    cnt = 0;
    T = target;
    S = numbers.size();
    dfs(0, 0, numbers, 0);

    answer = cnt;
    return answer;
}