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

문제 링크

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

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

주어진 숫자 배열에 있는 숫자를 각각 더하거나 빼서 타겟 넘버를 만드는 경우의 수를 구하는 문제.

풀이

재귀함수를 이용해서 모든 경우의 수를 다 해보아야한다.

현재 숫자를 value라고 했을 때 value값에 numbers배열에 있는 임의의 값 numbers[i] 를 더하거나 빼거나 2가지 경우로 생각할 수 있다. 모든 숫자를 사용해야한다고 했으므로 더하거나 빼거나 두가지 경우만 생각한다. 또한 모든 숫자를 쓰기전에 target 넘버를 완성하면 이때는 경우의 수로 생각하지 않는다.

이때 value의 초기값은 0이다.

재귀함수의 깊이(depth)가 배열에 있는 숫자의 총 개수와 같을 때, 모든 숫자를 이용했다는 뜻이다.

이때 현재 value가 target과 같으면 answer를  +1 해주고 아니면 그냥 리턴한다.

#include <string>
#include <vector>
 
using namespace std;
 
void dfs(int depth, vector<int> numbers, int value, int target, int &answer, int N){
    if(depth == N){
        if(value == target)
            answer++;
        return;
    }
    dfs(depth + 1, numbers, value + numbers[depth], target, answer, N); //더하거나
    dfs(depth + 1, numbers, value - numbers[depth], target, answer, N); //빼거나
}
 
int solution(vector<int> numbers, int target) {
    int answer = 0;
    dfs(0, numbers, 0, target, answer, numbers.size());
    return answer;
}