[Algorithm] 타겟 넘버 (Java)

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }    
    
    public int dfs(int[] numbers, int target, int count, int sum) {
        
        if(count == numbers.length) {
            if (sum == target) {
                return 1;
            }
            return 0;
        }
        
        return dfs(numbers, target, count + 1, sum + numbers[count]) + dfs(numbers, target, count + 1, sum - numbers[count]);
    }
}

• dfs 보다는 동적 계획법에 가까운 풀이법...

-arr[0] -arr[1]
        +arr[0]

+arr[0] -arr[1]
        +arr[0] ...

이런식으로 분기 처리를 해 나가면서 모든 경우의 수를 구하는 방법!