[백준]#1208 부분수열의 합 2

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

풀이

이 문제는 모든 경우의 수를 구하면 최악의 경우 2^40 이기 때문에 수열을 반으로 나눠서 구하면 더 적은 시간복잡도로 답을 구할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    static int N;
    static int[] arr;
    static HashMap<Integer, Integer> map;
    static int S;
    static long ans = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        S = Integer.parseInt(input[1]);
        map = new HashMap<>();
        arr = new int[N];

        input = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        combination(0, N/2, 0);
        combination(N/2, N, 0);

        if(map.containsKey(S))      //앞 배열로 S를 만들 수 있는 경우
            ans += map.get(S);

        System.out.println(ans);
    }


    public static void combination(int index, int len, int sum) {
        if(index==len)
            return;

        for(int i=index; i<len; i++) {
            int nSum = sum+arr[i];

            if(len==N/2) {                //반으로 나눈 앞 배열의 모든 부분수열 합 구하기
                if(map.containsKey(nSum)) {         //hashmap에 합 종류와 갯수 저장
                    map.put(nSum, map.get(nSum)+1);
                }

                else {
                    map.put(nSum, 1);
                }
            }

            else {
                if(map.containsKey(S-nSum)) {   //S에서 뒷 배열의 모든 부분수열의 합을 뺀 값이 hashmap에 존재하면 1증가
                    ans += map.get(S-nSum);
                }

                if(nSum==S)     //뒷 배열 만으로 S를 구할 수 있는 경우
                    ans++;
            }

            combination(i+1, len, nSum);
        }
    }
}