[伯俊]#1208部分数列の和2

質問する

N個の整数からなる数列があり、その数列のすべての要素のサイズがSである場合、整数を求めるプログラムが作成される.

入力

第1行は、整数個数を表すNおよび整数Sを与える.(1≦N≦40,|S|≦1000000)2行目にはN個の整数スペースがある.与えられた整数の節価は100000を超えない.

しゅつりょく

1行目と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);
        }
    }
}