[c++] 타겟 넘버 (프로그래머스 - dfs)

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

코딩테스트 연습 - 타겟 넘버

 

pass by reference로 answer 변수를 넘겨줘서 해결했는데

int dfs 로 return 1 했을 땐 결과가 나오지 않아서 슬퍼하는중

#include <string>
#include <vector>

using namespace std;

void dfs(vector<int> &numbers, int order, int maxOrder, int result, int target, int& answer) {
    if (order == maxOrder && result == target) {
        answer += 1;
        return;
    }
    else if (order == maxOrder) {
        return;
    }
    
    dfs(numbers, order + 1, maxOrder, result + numbers[order], target, answer);
    dfs(numbers, order + 1, maxOrder, result - numbers[order], target, answer);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    dfs(numbers, 1, (int)numbers.size(), numbers[0], target, answer);
    dfs(numbers, 1, (int)numbers.size(), -numbers[0], target, answer);
    
    return answer;
}

 

함수 int로 리턴하기 성공!!

#include <string>
#include <vector>

using namespace std;

int dfs(vector<int> &numbers, int order, int maxOrder, int result, int target) {
    int ret = 0;
    if (order == maxOrder && result == target) {
        return ret + 1;
    }
    else if (order == maxOrder) {
        return ret;
    }
    
    ret += dfs(numbers, order + 1, maxOrder, result + numbers[order], target);
    ret += dfs(numbers, order + 1, maxOrder, result - numbers[order], target);
    
    return ret;
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    answer += dfs(numbers, 1, (int)numbers.size(), numbers[0], target);
    answer += dfs(numbers, 1, (int)numbers.size(), -numbers[0], target);
    
    return answer;
}