[DFS/BFS] 타겟 넘버

|| 문제설명 ||

1. n개의 음이 아닌 정수가 있다.
2. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다.
3. 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성하라.

• numbers : 사용할 수 있는 숫자가 담긴 배열
• target : 타겟 넘버

_ 주어지는 숫자의 개수 : 2개 이상 20개 이하
_ 각 숫자 : 1 이상 50 이하, 자연수
_ 타겟 넘버 : 1 이상 1000 이하, 자연수

---

|| 문제해결방법 ||

- DFS로 모든 경우의 수를 찾아봄
- answer → 전역변수로 전환   
- 모든 경우에 있어 재귀함수를 통해 sum에 각 결과를 더함
- if (sum == target) 일 경우 answer++;
- numbers.size() == 0  이면 return;

---

|| 코드 ||

[2020.08.25] 성공

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int sum) {
    if(numbers.empty()) {
        if(sum == target) answer++;
        return;
    }
    int p = sum + numbers.back();
    int m = sum - numbers.back();
    numbers.pop_back();
    dfs(numbers, target, p);
    dfs(numbers, target, m);
}
int solution(vector<int> numbers, int target) {
    dfs(numbers, target, 0);
    return answer;
}

---

[2021.02.07]

class Solution {
    public int answer = 0;
    
    public void dfs(int num, int i, int[] numbers, int target) {
        if(i == numbers.length) {
            if(target == num) answer++;
            return;
        }
        dfs(num + numbers[i], i+1, numbers, target);
        dfs(num - numbers[i], i+1, numbers, target);
    }
    
    public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        
        return answer;
    }
}