프로그래머스 알고리즘 - 타겟 넘버

프로그래머스 알고리즘 - 타겟넘버

☞ 타겟 넘버 문제 링크

멱집합(모든 부분집합)을 구하는 방법을 응용하면 해당 문제를 풀기 수월 합니다. ☞ 멱집합(부분집합) 알고리즘

문제 풀이

• 첫번째 주어진 숫자로 덧셈(+)을 계산하거나, 혹은 뺄셈(-)을 진행합니다.
• → 두번째 주어진 숫자로 덧셈(+)을 계산하거나, 혹은 뺄셈(-)을 진행합니다.
• → . . . 
• → N번째 주어진 숫자로 덧셈(+)을 계산하거나, 혹은 뺄셈(-)을 진행합니다.

N번째까지 계산한 결과가 타겟 넘버와 같다면 answer을 하나 증가 시킵니다.

public class Solution {
    private static int answer = 0;
    public static void main(String[] args) {
        int[] numbers = {1, 1, 1, 1, 1};
        int target = 3;
        Solution solution = new Solution();
        System.out.println(solution.solution(numbers, target));
    }

    public int solution(int[] numbers, int target) {
        int[] flag = new int[numbers.length];
        findTargetNumber(numbers, target, flag, 0);
        return answer;
    }

    public static void findTargetNumber(int[] numbers, int target, int[] flag, int depth) {
        if (depth == numbers.length) {
            int sum=0;
            int max = numbers.length;
            for (int i = 0; i < max; i++) {
                if (flag[i] == 1) {
                    sum += numbers[i];
                } else {
                    sum -= numbers[i];
                }
            }
            if (sum == target) {
                answer++;
            }
            return;
        }

        //더하는경우
        flag[depth] = 1;
        findTargetNumber(numbers, target, flag, depth + 1);

        //빼는경우
        flag[depth] = 0;
        findTargetNumber(numbers, target, flag, depth + 1);
    }
}