MeetInTheMiddle.java

package Optimisation;
import java.util.*;

public class MeetInTheMiddle {

	public static long sumsLowerBound(long[] a, long b) {
		int n = a.length;
		int sizeL = 1 << (n / 2);
		int sizeR = 1 << (n - n / 2);
		long[] sumsL = new long[sizeL];
		long[] sumsR = new long[sizeR];
		for (int i = 0; i < sizeL; ++i)
			for (int j = 0; j < n / 2; ++j)
				if ((i & (1 << j)) > 0)
					sumsL[i] += a[j];
		for (int i = 0; i < sizeR; ++i)
			for (int j = 0; j < n - n / 2; ++j)
				if ((i & (1 << j)) > 0)
					sumsR[i] += a[j + n / 2];
		Arrays.sort(sumsL);
		Arrays.sort(sumsR);
		int left = 0;
		int right = sizeR - 1;
		long cur = Long.MIN_VALUE;
		while (left < sizeL && right >= 0) {
			if (sumsL[left] + sumsR[right] <= b) {
				cur = Math.max(cur, sumsL[left] + sumsR[right]);
				++left;
			} else {
				--right;
			}
		}
		return cur;
	}

	// Usage example
	public static void main(String[] args) {
		long[] a = { 1, 2, 5 };
		System.out.println(3 == sumsLowerBound(a, 4));
	}
}