[프로그래머스] 타겟 넘버(python/java)

문제 요약

• 주어진 배열의 순서를 바꾸지 않고, +/-를 이용하여 주어진 숫자가 나오도록 하는 방법을 구하라.

내가 생각한 로직

• 각각의 숫자가 +/-일 루트가 두 가지 가지로 쪼개진다.
• 마지막의 숫자를 더했을 때, 주어진 숫자가 나올 때, 방법 1가지가 나온다.

파이썬으로 제출한 정답

def solution(numbers, target):
    sup = [0]

    for i in numbers:
        sub = []
        for j in sup:
            sub.append(j + i)
            sub.append(j - i)
        sup = sub 

    return sup.count(target)

자바로 제출한 정답

class Solution {
    int answer = 0;

    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0);

        return answer;
    }

    public void dfs(int[] numbers, int depth, int target, int sum){
        if(depth == numbers.length){
            if(target == sum) answer++;
        } else {
            dfs(numbers, depth + 1, target, sum + numbers[depth]); 
            dfs(numbers, depth + 1, target, sum - numbers[depth]); 
        }
    }
}