[1208] 부분수열의 합2 <50%에서 통과못하고 있음...>

[yess98]

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

[1208] 부분수열의 합 2 문제를 풀고 있는데 채점해보면 50 % 정도에서 걸려 통과를 못하고 있어요 ㅜ
우선 n 개의 숫자들로 만들 수 있는 모든 부분 수열을 구해야하는데 n이 최대 40개로 시간초과가 예상되어 n을 반으로 나눠 각자의 부분수열의 합을 담은 리스트를 만들어줬습니다.

원하는 합 s가 0일때에는 공집합끼리의 합을 제외해줘야한다는 조건까지 놓치지 않은것 같은데
제가 놓치고 있는 부분을 찾지 못하고 있어요.

이 문제 푸신분들이나 제 코드에서 틀린 부분을 발견하신분들 알려주세요 !

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
	static StringBuilder sb; 
	static StringTokenizer st; 
	static int n ; 
	static int S; 
	static int num []; 
	static int cnt = 0 ; 
	static boolean [] check; 
	static ArrayList<Integer>al = new ArrayList<>(); 
	static ArrayList<Integer>al2 = new ArrayList<>(); 
	
	static void combi(int start, int end, int count , int target,int sum,  ArrayList<Integer> list ) {
		if(count == target) {
			list.add(sum); 
			return ; 
		}
		for(int i = start; i <= end; i ++) {
			if(!check[i]) {
				check[i] = true; 
				combi(i, end, count +1, target, sum + num[i], list); 
				check[i] = false; 
			}
		}
		
	}
	public static void main(String [] args) throws IOException {
	    // br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
	     st = new StringTokenizer(br.readLine()); 
	     n = Integer.parseInt(st.nextToken()); 
	     S = Integer.parseInt(st.nextToken()); 
	     num = new int [n + 1]; 
	     check = new boolean [n + 1]; 
	     st = new StringTokenizer(br.readLine()); 
	     for(int i = 1; i <= n ; i ++) {
	    	 num[i] = Integer.parseInt(st.nextToken()); 
	     }
	     int half = n/2; 

	     for(int target = 0 ; target <= half ; target ++ ) {
	    	 combi(1,half,0,target,0,al); 
	     }
	     for(int target = 0 ; target <= n - half ; target ++) {
	    	 combi(half + 1,n,0,target, 0 , al2); 
	     }
	     Collections.sort(al);
	     Collections.sort(al2,Collections.reverseOrder());
	   
	     int index1 = 0 ; 
	     int index2 = 0 ; 
	     while(true) {
	    	 if(index1 == al.size()  ||  index2 == al2.size()) {
	    		 break;
	    	 }
	    	 int sum = al.get(index1) + al2.get(index2); 
	    	 
	    	 if(sum == S) {
                         // 원하는 답이 나올 경우 
                         // 답을 만족하는 다른 경우들이 있는지 추가적으로 확인해줘야한다. 
	    		 int lc =  0 ; 
	    		 int lvalue = al.get(index1); 
	    		 while(index1 < al.size() && al.get(index1) == lvalue) {
	    			 lc ++; 
	    			 index1 ++; 
	    		 }
	    		 int rc = 0 ; 
	    		 int rvalue = al2.get(index2); 
	    		 while(index2 < al2.size() && al2.get(index2) == rvalue) {
	    			 rc ++; 
	    			 index2 ++; 
	    		 }
	    		 cnt  += lc * rc; 
	    	 }
	    	 else if(sum > S) {
	    		 index2 ++ ; 
	    	 }
	    	 else {
	    		 index1 ++; 
	    	 }
	    	
	     }
          
	     if(S == 0 ) {
	    	 bw.write(String.valueOf(cnt -1)); 
	     }
	     else {
	    	 bw.write(String.valueOf(cnt));
	     }
	     bw.flush();
	     bw.close();
	     br.close();
	     
	     
	}
}

[wjdgns7712]

long cnt = 0;
if(sum == S) {
  long lc =  0 ; 
  int lvalue = al.get(index1); 
  while(index1 < al.size() && al.get(index1) == lvalue) {
	  lc ++; 
	  index1 ++; 
  }
  long rc = 0 ; 
  int rvalue = al2.get(index2); 
  while(index2 < al2.size() && al2.get(index2) == rvalue) {
	  rc ++; 
	  index2 ++; 
  }
  cnt  += lc * rc; 

위와 같이 cnt, lc, rc의 타입을 long으로 바꿔줘야합니다.

주어진 배열의 길이가 40일때, 반으로 쪼갠 왼쪽 배열에서 생길 수 있는 조합의 수는 다음과 같이 생길 수 있습니다.

여기서 이 조합의 수가 모두 0인 경우가 생길 수 있습니다.

마찬가지로 오른쪽에서도 모두 0인 경우가 존재할 수 있는데,

이러한 경우에 S=0 이라면, lc = 2^20, rc = 2^20 이 되고,

cnt += lc * rc 이므로 cnt = 2^40이 되어

int범위를 초과해버립니다

[YeonsangYoon]

각 배열의 부분수열 자체가 S가 되는 경우도 고려해보셔야 할 것 같네요

	static void combi(int start, int end, int count , int target,int sum,  ArrayList<Integer> list ) {
		if(count == target) {
			list.add(sum); 
                        if (sum == S)
                                cnt++;
			return ; 
		}
		for(int i = start; i <= end; i ++) {
			if(!check[i]) {
				check[i] = true; 
				combi(i, end, count +1, target, sum + num[i], list); 
				check[i] = false; 
			}
		}
		
	}

[yess98]

@wjdgns7712 정훈님 ! 말씀하신대로 long자료형으로 바꾸니 해결되었어요 !! 감사합니다 ㅎ