알고리즘 문제 풀이(프로그래머스 - 타겟 넘버)

• DFS/BFS 알고리즘 문제 : 프로그래머스 LEVEL 2(타겟 넘버) - 사용 언어 : C++ - 해결 날짜 : 2021-01-15

  **- 해결 방법** :
  
      우선 numbers vector의 각 인덱스에 대해 DFS를 수행하여 sum에서 그 인덱스의 값을 뺀 값과 더한 값을 각각 재귀 호출하였다.
  
      모든 인덱스에 대한 접근을 완료한 후 그 값이 target과 일치할 때 answer를 증가시킨다.(index가 vertor의 범위를 벗어나면 점화식을 종료한다.)
  
      모든 DFS의 과정이 종료되면 target과 같을 때 마다 증가된 answer의 값을 반환하여 문제를 해결하였다.
  
  - 코드
  
  ```
  #include <string>
  #include <vector>
  
  using namespace std;
  int answer = 0;
  
  //모든 인덱스에 대해 뺀 값과 더한 값을 재귀
  void dfs(vector<int> numbers, int target, int sum, int index){
      if(index >= numbers.size()){ //index가 numbers vector의 범위를 벗어나면 점화식 종료
          if(sum == target){
              answer++;
          }
          return;
      }
      dfs(numbers, target, sum - numbers[index], index+1);
      dfs(numbers, target, sum + numbers[index], index+1);
  }
  
  int solution(vector<int> numbers, int target) {
      //numbers = 사용할 수 있는 숫자가 담긴 배열(2~20개/1~50의 숫자)
      //target = 타겟 넘버(1~1000)
      //answer = 타겟 넘버를 만드는 방법의 수
      dfs(numbers, target, 0, 0);
      return answer;
  }
  ```