[Java/부분집합] 백준 1208. 부분수열의 합2

🤔 Intuition

아이디어를 떠올리기 어려워 결국 다른 이의 풀이를 참고했다.
 
요지는, 전체 부분수열을 부분집합 알고리즘으로 탐색하게 되면 (2 ^ 40) 정도라서 시간을 초과하지만, 이를 절반씩 쪼개서 부분집합을 구하면 (2 * 2 ^ 20) 이라서 시간이 터지지 않는다. 따라서 이를 절반으로 쪼개어 부분수열의 합을 구한 뒤, 한쪽 절반의 부분수열의 합을 기준으로 다른 반쪽의 부분수열의 합과 더한 값이 S가 될 때의 개수를 세주면 된다.

🔎 Algorithm & Complexity

* @algorithm backtracking (powerset)
* @time O(2^N/2) : 976 ms
* @memory O(N) : 96908 KB

👨🏻‍💻 Logic

오른쪽 반 쪽의 부분수열의 합을 먼저 구해서, 합의 경우의 수를 map으로 저장해 줬다. (오른쪽 반 쪽을 저장해둘지 왼쪽 반 쪽을 저장해둘지는 푸는 사람 마음대로 기준을 정하면 된다.)
왼쪽 반 쪽의 부분수열을 진행하면서, 왼쪽 부분수열의 합을 leftPS라고 한다면 map.get(S - leftPS)의 총 합이 부분수열의 합이 S인 경우의 수가 된다.
단, 둘다 아무것도 고르지 않는 경우가 1로 추가되는데 문제 조건상 부분수열의 크기가 양수여야 하므로 만약 S가 0일 때에는 이를 카운트하게 되는 것을 주의해야 한다.

public class BOJ_1208_부분수열의합2 {
    private static HashMap<Integer, Integer> map = new HashMap<>();
    private static long ans = 0;
    private static int S;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        ps(arr, new boolean[N], N / 2, N);
        ps2(arr, new boolean[N], 0, N / 2);
        if (S == 0) {
            ans--;
        }
        System.out.println(ans);
    }

    private static void ps(int[] arr, boolean[] selected, int depth, int N) {
        if (depth == N) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                if (selected[i]) {
                    sum += arr[i];
                }
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            return;
        }
        selected[depth] = true;
        ps(arr, selected, depth+1, N);
        selected[depth] = false;
        ps(arr, selected, depth+1, N);
    }
    private static void ps2 (int[] arr, boolean[] selected, int depth, int N) {
        if (depth == N) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                if (selected[i]) {
                    sum += arr[i];
                }
            }
            ans += map.getOrDefault(S - sum, 0);
            return;
        }
        selected[depth] = true;
        ps2(arr, selected, depth + 1, N);
        selected[depth] = false;
        ps2(arr, selected, depth + 1, N);
    }
}