[백준 알고리즘 - 1208] 부분집합의 합 2 - java/재귀호출

크기가 n인 집합이 주어졌을 때, 그 부분집합의 갯수는 2^n이다.

이 문제에서 최대 N은 40이기 때문에 2^40=1.0995116e+12

어느정도인지는 모르겠고, 1초 안에 해결할 수 없는 크기인건 알겠다.

따라서 이 문제는 분할하여 풀어야한다.

2^20은 약 1000000으로 1초안에 계산할 수 있기 때문에

주어진 집합을 반으로 쪼개어서 각각 구한 후 풀이한다.

풀이과정은 다음과 같다.

[ A, B, C, D, E, F ] 집합이 주어졌을 때,

[ A, B C ] [ D, E, F ] 로 쪼갠다.

분할된 두 집합의 부분집합을 구한 후(공집합 포함) 두 분할을 활용하면 문제를 풀이할 수 있다.

여기서 공집합을 포함하는 이유는 앞의 부분집합의 공집합을 선택할지라도 뒤에서 공집합이 아닌 집합을 선택하면 결과적으로 그 부분집합은 공집합이 아니기 때문이다.

따라서, 공집합 제외라는 예외처리는 둘다 0인 경우를 빼야하는데, S가 0으로 주어졌을 때 공집합을 함께 구하게 되므로 1만큼만 빼주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static void makePre(int[] arr, int idx, int e, int sum, ArrayList<Integer> array) {
		if(idx>= e)//끝까지 다 돌았다면
		{
			array.add(sum);//추가
			return;
		}

		
		makePre(arr, idx+1, e, sum, array);//현재 인덱스를 포함할 때
		
		makePre(arr, idx+1, e, sum+arr[idx], array);//현재 인덱스를 포함하지 않을 때
		
		
	}
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stringTokenizer=new StringTokenizer(br.readLine());
    	int N= Integer.parseInt(stringTokenizer.nextToken());
    	int S=Integer.parseInt(stringTokenizer.nextToken());
    	
    	int[] arr=new int[N];
    	
    	stringTokenizer=new StringTokenizer(br.readLine());
    	int k=0;
    	while(stringTokenizer.hasMoreTokens())
    		arr[k++]=Integer.parseInt(stringTokenizer.nextToken());
    	
    	ArrayList<Integer> first_arr=new ArrayList<>();
    	ArrayList<Integer> second_arr=new ArrayList<>();
    	
    	makePre(arr,0,N/2, 0, first_arr);
    	
    	makePre(arr,N/2, arr.length, 0, second_arr);
    	
    	Collections.sort(first_arr);
    	Collections.sort(second_arr);
    	

    	
    	int left=0; 
    	int right=second_arr.size()-1;
    	
    	long ans=0;
    	
    	while(left < first_arr.size() && right >=0) {
    		long ls=first_arr.get(left);
    		long rs=second_arr.get(right);
    		
    		if(ls+rs == S) {//S와 일치하면,  각 분할 집합에서 해당 합을 지니는 원소의 개수를 셈
    			long lc=0; 
    			while(  left<first_arr.size() && first_arr.get(left)== ls) {
    				lc++;
    				left++;
    			}
    			
    			long rc=0;
    			while( right >=0 && second_arr.get(right)== rs) {
    				rc++;
    				right--;
    			}
    				
    			ans+=lc*rc;   			
    		}
    		
    		if(ls+rs > S)
    			right--;
    		if(ls+rs < S)
    			left++;
    		
    	}
    	
    	if(S==0) {
    		ans-= 1;
    	}
    	
    	System.out.println(ans);
    	
    
    	
    	  	
    	
    }
}