부분 수열의 합2

https://www.acmicpc.net/problem/1208

풀이

음수도 있어 기존의 부분 수열을 구해서 답을 구하는 것은 어렵다고 생각했다. 그래서 백준 알고리즘 분류를 확인했더니 중간에서 만나기라고 되어있어 이게 무엇인지 검색해서 개념을 잡고 풀이했다.

먼저 주어진 수열을 반으로 나누어 각각 모든 부분 수열에 대한 합들을 구한다. 이를 leftSum, rigthSum으로 해서 차이를 기반으로 인덱스를 옮겨가면서 풀 수가 있다.

또 map을 이용해 합을 키로 하고 해당 키가 나온 횟수를 value로 하여 leftSum을 구현하고 답을 구할 때 leftSum.get(s-rightSum)을 더해주는 방법을 사용할 수 있다.

아래 코드는 두번째 방법을 이용해 구현하였다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
    static int n, s;
    static HashMap<Integer, Integer> leftSum = new HashMap<>();
    static ArrayList<Integer> rightSum = new ArrayList<>();
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        s = Integer.parseInt(input[1]);

        arr = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }

        leftSubSet(0, 0);
        rightSubSet(n / 2, 0);

        long ans = 0;
        for (int a : rightSum) {
            if(a == s) {
                ans++;
            }
            if (leftSum.containsKey(s - a)) {
                ans += leftSum.get(s - a);
            }
        }

        if(leftSum.containsKey(s)) {
            ans += leftSum.get(s);
        }

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void leftSubSet(int start, int sum) {
        for (int i = start; i < n / 2; i++) {
            if (leftSum.containsKey(sum + arr[i])) {
                int num = leftSum.get(sum + arr[i]);
                leftSum.put(sum + arr[i], num + 1);
            } else
                leftSum.put(sum + arr[i], 1);
            leftSubSet(i + 1, sum + arr[i]);
        }
    }

    private static void rightSubSet(int start, int sum) {
        for (int i = start; i < n; i++) {
            rightSum.add(sum + arr[i]);
            rightSubSet(i + 1, sum + arr[i]);
        }
    }

}