[C++] 프로그래머스 : 타겟 넘버

#include <string>
#include <vector>
using namespace std;

bool visited[21] = {0}; // 방문 여부
int Numbers[21] = {0}; // 숫자 저장
int arrSize;
int Target;

int cnt = 0;
bool flag = true; // 모두 탐색 되었는지 검사

//백트래킹
void DFS(int idx, int tmp){
    if(tmp == Target && idx == arrSize){  
        for(int j = 0; j < arrSize; j++){
            if(visited[j] == 0){
                flag = false;
            }
        }
        
        if(flag){
            cnt++;
        } else {
            flag = true; // 초기화
        }
        return;
    }
    
    for(int i = idx; i < arrSize; i++){
        visited[i] = 1;
        DFS(i+1, tmp - Numbers[i]);
        DFS(i+1, tmp + Numbers[i]);
        visited[i] = 0;
    }
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    for(int i = 0; i < numbers.size(); i++){
        Numbers[i] = numbers[i]; // 벡터 복사
    }
    arrSize = numbers.size();
    Target = target;
    
    DFS(0, 0); // 첫 숫자부터 값 0부터 시작
    
    answer = cnt;
    
    return answer;
}

이제 가벼운 백트래킹 정도는 인터넷을 보지 않고 풀 수 있다. 굿

프로그래머스 환경에서 코테를 칠 일이 생겨서 풀어보는 중인데 아 굉장히 어색하다.
특히 모든 수가 parameter로 주어져서 전역변수로 사용하려면 따로 재할당을 해야하는 일이 말이다.

백트래킹을 이용해서 모든 경우의 수를 탐색해가면서 값을 구한다. 0부터 시작해서 하나씩 수를 탐색하면서 - 하거나 + 를 해준다. 만약 모든 수가 탐색 완료(- 또는 + 연산이 수행되었다는 뜻이다.) 되었고 결과값이 target 값과 같으면 어찌되었든 -, +를 조합해서 target 값을 만들어내었다는 의미가 된다. 백트래킹의 경우 절대 중복되는 결과값을 가지지 못하므로 모두 visited 된 경우만 세어서 cnt++ 해준다.