324. 타겟 넘버

프로그래머스

1. Python

def dfs(numbers, target, n, result):
    global answer
    if n == len(numbers):
        if result == target:
            answer += 1
        return
    else:
        dfs(numbers, target, n + 1, result + numbers[n])
        dfs(numbers, target, n + 1, result - numbers[n])

def solution(numbers, target):
    global answer
    answer = 0
    dfs(numbers, target,0,0)
    return answer

bfs

#https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

2. C++

#include <string>
#include <vector>

using namespace std;

int answer = 0;

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

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

3. JavaScript

function solution(numbers, target) {
    var answer = 0;
    function dfs(n, result){
        if (n == numbers.length){
            if (result == target){
                answer++;
            }
        }else{
            dfs(n + 1, result + numbers[n])
            dfs(n + 1, result - numbers[n])
            
        }
        
    }
    dfs(0, 0)
    return answer;
}