[Programmers/C++] 타겟 넘버

 

문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 

• 재귀 함수를 이용한 깊이우선탐색(DFS)을 구현했다.
• 재귀 함수의 탈출 조건은 탐색 대상인 인덱스를 벗어났을 때이다.
• 탈출 전, 문제에서 원하는 타겟 넘버가 만들어졌는지 비교한다. 

#include <vector>
using namespace std;

vector<int> _numbers;
int _target;
int _answer;

void dfs(int idx, int sum) {
    //. 탈출 조건
    if (idx == _numbers.size()) {
        if (sum == _target){
            _answer++;
        }

        return;
    }

    dfs(idx + 1, sum + _numbers[idx]);
    dfs(idx + 1, sum - _numbers[idx]);
}

int solution(vector<int> numbers, int target) {
    _answer = 0;
    _numbers = numbers;
    _target = target;

    dfs(0, 0);	// dfs(idx: 0번 인덱스부터 탐색, sum: 총 합은 0으로 초기화)

    return _answer;
}

 

 

 

---