프로그래머스 : 타겟넘버

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 문제 설명 

 

문제는 vector로 여러가지 숫자를 입력받고 vector 의 숫자들을 더하거나 빼서 타겟  숫자로 만드는것.

처음에 놓쳤던 것은 vector의 숫자를 모두다 이용해야되는건데 중간에 target  넘버가 나오면 종료 시켜서 조금 헤맸다.

 

 알고리즘 

 

1. 재귀함수를 이용한 완탐으로 +와 -경우 두가지로 나누어 진행

 

 코드 

#include<iostream>
#include<vector>
 
using namespace std;
 
int result = 0;
 
void func(int a, int cnt, vector<int> numbers, int target) {
    
    //종료부
    if (cnt == numbers.size()) {
        //타겟과 일치하면 결과값 +1
        if (a == target) result++;
        return;
    }
    
    //양수로 보내기
    func(a + numbers[cnt], cnt + 1, numbers, target); 
 
    //음수로 보내기
    func(a - numbers[cnt], cnt + 1, numbers, target);
 
}
 
int solution(vector<int> numbers, int target) {
    func(0, 0,numbers, target);
    int answer = result;
    return answer;
}