문제

문제링크

접근

• dfs을 응용하여 풀었다. 모든 값이 1로 초기화 되어있는 배열을 선언한 뒤, dfs로 각 경우의 수를 방문하면서 -1로 그 자리를 바꾸도록 하였다.
• 그럼 부호의 모든 경우의 수를 방문할 수 있으며, 방문할 때마다 각 자리의 수를 곱해서 더하였다.
• 중복된 경우의 수가 답에 반영될 수 있으니 dfs 내의 반복문 시작점이 0이 아니라 다음 인덱스라는 점을 조심해야 한다.

소스 코드

class Main {
    public static void main(String[] args) throws Exception {
        int[] numbers = {1, 1, 1, 1, 1};
        int target = 3;
        Solution sol = new Solution();

        System.out.println("result : " + sol.solution(numbers, target));
    }
}

class Solution {
    int length;
    int[] ops;
    int[] numbers0;
    int answer = 0, target0 = 0;

    public int solution(int[] numbers, int target) {
        length = numbers.length;
        ops = new int[length];
        Arrays.fill(ops, 1);
        numbers0 = numbers;
        target0 = target;

        dfs(-1);

        return answer;
    }

    public void dfs(int idx) {
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += numbers0[i] * ops[i];
        }
        if (sum == target0) {
            answer++;
        }

        for (int i = idx+1; i < length; i++) {
            if (ops[i] == 1) {
                ops[i] = -1;
                dfs(i);
                ops[i] = 1;
            }
        }
    }
}