중복순열. 타겟넘버

문제

N개의 수가 주어지는데, 처음 원소 앞까지 포함해서 N개의 기호( + , - )를 넣어서 target과 일치하게 만드는 경우의 수를 구하는 문제.

해결방향성

일단 나는 백트래킹, 중복 순열로 해결하였다. swea의 숫자카드배열과 비슷한 문제. operCount--, ++ 자체가 visited 역할을 한다. 0보다 작아지면 접근이 불가능.

코드

import java.io.*;
class Solution {
    static int total = 0;
    static int[] arr;
    static int N;
    // 중복 순열
    public int solution(int[] numbers, int target) { //
        N = numbers.length;

        int[] operCount = new int[2];
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            operCount[0] = N - i; // N부터 : 앞에도 붙을수있다.
            operCount[1] = i; // 0부터
            perm2(0, numbers, target, operCount);
        }

        return total;
    }

    private void perm2(int cnt, int[] numbers, int target, int[] operCount) {
        if (cnt == N) {
            if (summation(numbers) == target) {
                total++;
            }
            return;
        }
        // 중복 뽑기됨.
        for (int i = 0; i < 2; i++) { // 0, 1
            if (operCount[i] > 0) { // 0보다 커야 arr에 포함시킴
                operCount[i]--;
                arr[cnt] = i + 1; // 1 , 2
                perm2(cnt + 1, numbers, target, operCount);
                arr[cnt] = 0;
                operCount[i]++;
            }
        }
    }

    private int summation(int[] numbers) {
        int sum = 0;
        for (int i = 0; i < N; i++) { // 연산수대로 돔.
            if (arr[i] == 1) { // +
                sum += numbers[i];
            }
            if (arr[i] == 2) { // -
                sum -= numbers[i];
            }
        }
        return sum;
    }
}

결론

백트래킹으로 해결하였지만, 부분집합을 써도 해결할수있었던 문제. 부분집합을 사용하면 코드가 꽤 간단해져서, 부분집합을 사용하면 어땟을까하는 생각이 들었다.