프로그래머스: 타겟 넘버

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

프로그래머스

코드

#include <bits/stdc++.h>
using namespace std;
const int dy[2]={1,-1};
int ret;
void dfs(int depth, int value, vector<int> numbers, int target){
    if(depth == numbers.size()){ //종료조건
        if(value==target) ret++;
        return;  
    } 
    for(int j=0;j<2;j++){ //+또는 -
        dfs(depth+1, value +(dy[j]*numbers[depth]), numbers, target);
    }
    
}


int solution(vector<int> numbers, int target) {
    int answer = 0;
    //dfs 수행
    dfs(1, numbers[0], numbers, target);
    dfs(1, -numbers[0], numbers, target);
    answer=ret;
    return answer;
}

 

dfs문제이다. visited 배열을 사용하면 너무 경우의 수가 많아지고 딱히 쓸 필요가 없기때문에 (위치가 중요한 것이 아님) visited 배열로 중복 체크하지않고 재귀를 사용했다.