[Programmers] 타겟 넘버

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

프로그래머스

 

1. Python

def solution(numbers, target):
    ret = 0
    def dfs(i, acc):
        nonlocal ret, target
        if i == len(numbers):
            ret += acc == target
            return
        dfs(i+1, acc+numbers[i])
        dfs(i+1, acc-numbers[i])
    dfs(0, 0)
    return ret

 

2. C++

int ret {0};


void dfs(const vector<int>& numbers, int target, int acc, int idx) {
	if (idx == numbers.size()) {
		ret += target == acc;
		return;
	}
	dfs(numbers, target, acc+numbers[idx], idx+1);
	dfs(numbers, target, acc-numbers[idx], idx+1);
}


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