타겟 넘버

문제 (프로그래머스 43165 : 타겟 넘버)
43165 : 타겟 넘버

별도 문제 설명 생략

문제파악

• 주어진 parameter : 정수형 배열 numbers, 정수 target
• 음이 아닌 정수형 배열 numbers가 주어지고, 더하거나 빼서 target을 만들수 있는 경우의 수를 구하는것

접근방법

• 가장 앞의 원소를 기준으로 뒤의 원소를 더하거나 빼보기
• 재귀 활용 => 완전 탐색 = dfs
• 모든 원소를 사용했을때 탈출
  

코드구현

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
		return dfs(numbers, 0, target, 0);    
    }
    
    int dfs(int[] numbers, int index, int target, int cur){
    	// 기저 조건 
        if(index == numbers.length){
        	return (target==cur)? 1:0;
        }
        
        int sum = 0 ;
        sum += dfs(numbers, index + 1, target, cur + numbers[index]);
        sum += dfs(numbers, index + 1, target, cur - numbers[index]);
        return sum;
    }
}

배운점

1. 완전 탐색의 방식 : 재귀를 사용

• 재귀를 사용하는데 필요한 조건 : 1) 기저조건 2) 반복조건

다른 방법은 없을까?