[프로그래머스/C++]Lv.2 - 타겟 넘버

문제 링크

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

시도한 방법

바로 전 문제에서 배운 재귀를 써보려다가 막혔다. 모든 수를 더하거나 빼보는것을 해보기 보다 sum이 target보다 크면 현재 숫자를 빼고 작으면 더하는 방법을 사용했었다.

다른 사람의 풀이

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int>& numbers, int target, int index, int sum, bool sign)
{
    if(sign)
        sum += numbers[index++];
    else
        sum -= numbers[index++];
    
    if(index == numbers.size())
    {
        if(sum == target)
            answer++;
    }
    else
    {
        dfs(numbers, target, index, sum, true);
        dfs(numbers, target, index, sum, false);
    }
}

int solution(vector<int> numbers, int target) {
    
    dfs(numbers, target, 0, 0, true);
    dfs(numbers, target, 0, 0, false);
    
    return answer;
}

다른 사람의 풀이 해석

재귀함수를 쓰는데 더하거나 빼는 경우를 모두 재귀함수화 하여 구하였다.