[프로그래머스] 타겟 넘버

문제

 

 

 

분석

완전 탐색 문제이다 정수인 1 을 바꿔 가면서 더하기 빼기를 해준다.

그러다가 5개를 다 더했을때 값이 원하는 값이면 1을 더해 준다.

 

완전 탐색인데 단순 완전 탐색이 아니라 음수 양수를 따져서 탐색을 해줘야 한다.

그렇다면 어떻게 하면 될까?

 

재귀 함수로 구현을 한다.

인덱스를 증가 해주면서

재귀함수안에서 두번 호출을 해준다.

정수일때와 음수 일때. 

 

아래 그림 처럼 리턴이 될때 정수 음수 번갈아 가며 탐색을 한다.

 

 

 

구현

import java.util.*;

class Solution {
    
    public int solve(int[] numbers, int target, int sum, int idx) {

        if (idx == numbers.length) {
           if(sum == target)  {
                return 1;    
            } else  {
                return 0;
            }
        }
        
       
        int result = 0;        
        result += solve(numbers, target, sum+numbers[idx], idx+1);
        result += solve(numbers, target, sum-numbers[idx], idx+1);
        return result;
    }
    
    public int solution(int[] numbers, int target) {

        int answer = 1;
 
        answer = solve(numbers, target, numbers[0], 1) + solve(numbers, target, -numbers[0], 1);

        return answer;
    }
}

 

 

 

결과