프로그래머스 - 타겟 넘버 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int cnt=0;

void D(int target,vector<int>num,int n,int i)
{
    if(i==num.size())
    {
        if(n==target)cnt++;
        return;
    }
    
    
    D(target,num,n+num[i],i+1);
    D(target,num,n-num[i],i+1);
}

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

설명

재귀함수를 이용한 DFS로 풀었다. 

numbers 의 모든 수에 대해서 각각 더하고 뺀 결과를 모두 보고 target과 비교해야 하기 때문에 DFS를 사용하였다. 

 

DFS를 모르는 분들은 아래 두 사이트를 참고하시기 바랍니다.  https://velog.io/@crystalhwang16/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-BFS%EC%99%80-DFS 

완전탐색, BFS와 DFS

https://gamedevlog.tistory.com/49

백트래킹(back tracking)

p.s 재귀가 아닌 반복문으로 푸는 방법이 궁금한데, 아직 잘 모르겠다. 

아시는 분은 설명이나 조언 부탁드립니다!