subset sum problem in SPOJ

SubsetSum.java

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

class Main {

	private static Scanner sc;
	
	// input number in array of size N
	private static long[] input(int N){

		long array [] = new long[N];
		for(int i=0;i<N;i++){
			array[i] = sc.nextLong();
		}

		return array;
	}
  	
	// find all subset sum of array
	private static Long[] findSubsetSum(long[] array){

		int N = array.length;
		int range = 1<<N;
		Long [] result = new Long[range];

		for(int i=0;i<range;i++){
			long sum=0;
			for(int j=0;j<N;j++){
				if((i&(1<<j))>0){
					sum+=array[j];
				}
			}
			result[i]=sum;
		}
		return result;
	}
 
	public static void main(String abc[]) {

		int N; // N is size of array
		sc = new Scanner(System.in);
		N = sc.nextInt();

		long A,B; 
		A = sc.nextLong();
		B = sc.nextLong();

		int N1 = N/2;
		int N2 = N-N1;
		// input the array in to 2 halves of size N/2 each
		long []v1 = input(N1);
		long []v2 = input(N2);
 		
		// find the subset sum for each half
		Long[] sv1 = findSubsetSum(v1);
		Long[] sv2 = findSubsetSum(v2);
		
		// for binary search, sort sv2
		Arrays.sort(sv2);
 
		long ans=0;
		for(int i=0;i<sv1.length;i++){

			long start = A - sv1[i];
			long end = B - sv1[i];
 
			int low = Arrays.binarySearch(sv2, start, new Comparator<Long>(){
				public int compare(Long a, Long b){
					return a>=b ? 1: -1;
				}
			}); // lower bound
			int hi = Arrays.binarySearch(sv2, end, new Comparator<Long>() {

				public int compare(Long a, Long b){
					return a>b ? 1 : -1;
				}
			}); // upper bound

			// fetch the actual index 
			int lv1 = (low>=0) ? low : ~low;
			int lv2 = (hi>=0) ? hi : ~hi; 
			
			// check for edge case
  			lv2 = (lv2==sv2.length) ? lv2-- : lv2;
			lv1 = (lv1==sv2.length) ? lv1-- : lv1;
 
			 ans += (lv2-lv1);
		}
		System.out.println(ans);
	}
}