타겟 넘버

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=cpp

프로그래머스

문제 설명: 벡터의 원소들의 값을 +, -을 통해 연산한 값의 경우의 수 중 target값과 동일 한 값들의 갯수를 구하는 문제.

 

로직: dfs (bottom up)

branch: +, -  2개
level: numbers 갯수까지.
sum을 통해 branch(+, -)와 level(numbers 값들)에 따라 모든 연산의 경우의 수가 나오는데  numbers이 길이까지 level이 내려가서 
sum값이 target값과 같을 떄 cnt++ 

#include <string>
#include <vector>
#include<iostream>
using namespace std;
int cnt = 0;
void recursion(vector<int>num, int lv, int target, int sum) {
    if (lv == num.size()) { // lv이 leaf 노드까지 내려갈때 (level 끝까지 내려갈때)
        if (sum == target) {  // sum이 타겟 값과 동일 시
            cnt++;
            return;
        }
        return;
    }
    // 재귀 +연산
    recursion(num, lv + 1, target, sum + num[lv]);  // lv + 1한 이유 : numbers사이즈가 depth이기에 lv + 1을 통해 그 depth까지 내려감, num[lv]을 통해 numbers 각 인덱스의 값에 접근. 
    // 재귀 -연산
    recursion(num, lv + 1, target, sum - num[lv]);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    recursion(numbers, 0, target, 0);
    answer = cnt;
    return answer;
}
int main(void) {
    solution({ 4,1,2,1 }, 4);
}