Sumset (POJ 2549)

At first we have . The order of , and can be arbitrary exchanged so we let . Then the order of in increasing order may be , , , . For the first two cases we iterate 's values first and put it into HashSet for quick query and then iterate and to check if there is a combination that makes . Conversely for the last two cases, we iterate 's values and uses and to find combinations.

import java.io.*;
import java.util.*;

public class Sumset {
    private static void solve(long[] array) {
        int N = array.length;
        HashSet<Long> set = new HashSet<Long>(N * (N - 1));
        int mindex = -1;
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < a; b++) {
                set.add(array[a] + array[b]);
            }

            int c = a + 1;
            for (int d = c + 1; d < N; d++) {
                if (set.contains(array[c] - array[d])) mindex = Math.max(mindex, c);
                if (set.contains(array[d] - array[c])) mindex = Math.max(mindex, d);
            }
        }
        set.clear();
        for (int a = N - 1; a >= 0; a--) {
            for (int b = a + 1; b < N; b++) {
                set.add(array[a] + array[b]);
            }

            int c = a - 1;
            for (int d = 0; d < c; d++) {
                if (set.contains(array[c] - array[d])) mindex = Math.max(mindex, c);
                if (set.contains(array[d] - array[c])) mindex = Math.max(mindex, d);
            }
        }
        if (mindex < 0) System.out.println("no solution");
        else System.out.println(array[mindex]);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(true) {
            int N = in.nextInt();
            if (N == 0) break;
            TreeSet<Long> set = new TreeSet<Long>();
            for (int i = 0; i < N; i++) {
                set.add(in.nextLong());
            }
            long[] array = new long[set.size()];
            Iterator<Long> iter = set.iterator();
            for (int i = 0; i < array.length; i++) {
                array[i] = iter.next();
            }
            solve(array);
        }
    }
}