[프로그래머스] 타겟 넘버 (C++)

 

문제

프로그래머스

 

미 문제는 입력 받은 숫자들을 + - 하여 목표 숫자를 만들 수 있는 경우의 수를 반환하는 문제이다.

---

풀이

재귀 함수를 사용해 모든 경우의 수를 탐색하고, 마지막 숫자에 도달했을 때 목표 숫자와 일치하는 경우 answer 값을 증가시키는 방식으로 문제를 풀이했다.

#include <string>
#include <vector>

using namespace std;

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

int answer = 0;

void Solution(int curNum , int target ,int curStep, vector<int> numbers){
    if(curStep == numbers.size() - 1){
        if (curNum == target)
            answer++;
        return;
    }

    curStep++;

    Solution(curNum + numbers[curStep], target, curStep, numbers );
    Solution(curNum - numbers[curStep], target, curStep, numbers );
}

int solution(vector<int> numbers, int target) {

    Solution(numbers[0], target, 0, numbers);
    Solution(-numbers[0], target, 0, numbers);

    return answer;
}