[자바] 프로그래머스 - 타겟 넘버 (코딩테스트 연습 Lv2)

문제 : Programmers-타겟넘버

 

 

  결국 주어진 numbers를 순서대로 + 한번, - 한번씩 모든 경우를 구해보면 된다. 이 경우 O(2^n)이 된다(+,-의 2가지 경우를 n번 봐야 하므로).

 

  예를들어 numbers가 [1, 2, 3]일 경우 다음과 같이 진행된다.

이 중 target과 동일한 경우를 세서 return해주면 된다.

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    int cnt = 0;
    private void rec(int[] numbers, int target, int idx, int sum) {
        if (idx == numbers.length) {
            if (sum == target)
                cnt++;
            return;
        }
        rec(numbers, target, idx+1, sum+numbers[idx]);
        rec(numbers, target, idx+1, sum-numbers[idx]);
    }
    public int solution(int[] numbers, int target) {
        rec(numbers, target, 0, 0);
        return cnt;
    }
}