[문제풀이] 타겟 넘버

📢 문제

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

📢 알고리즘

dfs, 백트래킹

• 2차원 배열이 주어지거나 2차원 벡터로 직접 연결리스트 만드는 경우 말고, 이런 경우도 dfs 이용하는구나..
  • 백트래킹 : 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 사용한다.
• 가능한 경우를 그려보면 그래프 모양이 나옴 -> 그 경우를 모두 한번씩 방문해가며 조건에 맞는 경우의 개수를 찾는 문제
  • 나는 중첩for문을 이용하는 생각을 했지만, 잘 생각해보면 불가능.. dfs로 가능~!

📢 풀이

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(int sum, int count, vector<int> numbers, int target) {
    int len = numbers.size();
    if(count == len) {
        if(sum == target) {
            answer++;
        }
        return;
    }
    dfs(sum+numbers[count], count+1, numbers, target);
    dfs(sum-numbers[count], count+1, numbers, target);
}


int solution(vector<int> numbers, int target) {
    dfs(0, 0, numbers, target);
    return answer;
}

https://yong-nyong.tistory.com/41