/**
 * User: uerturk
 */
 
import java.util.*;
 
/**
 * Input - array of integers size N, integer Threshold.
 * Output - the pairs (x, y) of distinct elements with condition x + y <= Threshold.
 * Is that possible to implement is with O(n) ?
 */
class FindPairsUnderThreshold {
 
 
    public List<Map.Entry<Integer, Set<Integer>>> solve(Integer[] integers, Integer threshold) {
 
        // the complexity > O(n), sorted list is the key in this solution
        SortedSet<Integer> sortedSet = new TreeSet<Integer>();
 
        // first put values into the sorted set
        for (Integer number : integers) {
            sortedSet.add(number);
        }
 
        // then get the range from the head (smallest value) to the maximum value that satisfies the condition
        List<Map.Entry<Integer, Set<Integer>>> result = new ArrayList<Map.Entry<Integer, Set<Integer>>>();
        for (Integer number : integers) {
            // headSet is not inclusive, +1 is to make it include the exact sum
            int diff = threshold - number + 1;
            Set<Integer> integerIntegerSortedMap = sortedSet.headSet(diff);
 
            Map.Entry<Integer, Set<Integer>> integerSetPair = new AbstractMap.SimpleEntry<Integer, Set<Integer>>(number, integerIntegerSortedMap);
            result.add(integerSetPair);
        }
        return result;
    }
 
 
    public static void main(String[] args) {
        Integer[] integers = {4, 1, 5, 2, 3, -1, 6,};
        Integer threshold = 4;
        List<Map.Entry<Integer, Set<Integer>>> solution = new FindPairsUnderThreshold().solve(integers, threshold);
        for (Map.Entry<Integer, Set<Integer>> entry : solution) {
            Integer first = entry.getKey();
            for (Integer second : entry.getValue()) {
                System.out.print("(" + first + ", " + second + "), ");
            }
        }
    }
 
}
 

LyoqCiAqIFVzZXI6IHVlcnR1cmsKICovCgppbXBvcnQgamF2YS51dGlsLio7CgovKioKICogSW5wdXQgLSBhcnJheSBvZiBpbnRlZ2VycyBzaXplIE4sIGludGVnZXIgVGhyZXNob2xkLgogKiBPdXRwdXQgLSB0aGUgcGFpcnMgKHgsIHkpIG9mIGRpc3RpbmN0IGVsZW1lbnRzIHdpdGggY29uZGl0aW9uIHggKyB5IDw9IFRocmVzaG9sZC4KICogSXMgdGhhdCBwb3NzaWJsZSB0byBpbXBsZW1lbnQgaXMgd2l0aCBPKG4pID8KICovCmNsYXNzIEZpbmRQYWlyc1VuZGVyVGhyZXNob2xkIHsKCgogICAgcHVibGljIExpc3Q8TWFwLkVudHJ5PEludGVnZXIsIFNldDxJbnRlZ2VyPj4+IHNvbHZlKEludGVnZXJbXSBpbnRlZ2VycywgSW50ZWdlciB0aHJlc2hvbGQpIHsKCiAgICAgICAgLy8gdGhlIGNvbXBsZXhpdHkgPiBPKG4pLCBzb3J0ZWQgbGlzdCBpcyB0aGUga2V5IGluIHRoaXMgc29sdXRpb24KICAgICAgICBTb3J0ZWRTZXQ8SW50ZWdlcj4gc29ydGVkU2V0ID0gbmV3IFRyZWVTZXQ8SW50ZWdlcj4oKTsKCiAgICAgICAgLy8gZmlyc3QgcHV0IHZhbHVlcyBpbnRvIHRoZSBzb3J0ZWQgc2V0CiAgICAgICAgZm9yIChJbnRlZ2VyIG51bWJlciA6IGludGVnZXJzKSB7CiAgICAgICAgICAgIHNvcnRlZFNldC5hZGQobnVtYmVyKTsKICAgICAgICB9CgogICAgICAgIC8vIHRoZW4gZ2V0IHRoZSByYW5nZSBmcm9tIHRoZSBoZWFkIChzbWFsbGVzdCB2YWx1ZSkgdG8gdGhlIG1heGltdW0gdmFsdWUgdGhhdCBzYXRpc2ZpZXMgdGhlIGNvbmRpdGlvbgogICAgICAgIExpc3Q8TWFwLkVudHJ5PEludGVnZXIsIFNldDxJbnRlZ2VyPj4+IHJlc3VsdCA9IG5ldyBBcnJheUxpc3Q8TWFwLkVudHJ5PEludGVnZXIsIFNldDxJbnRlZ2VyPj4+KCk7CiAgICAgICAgZm9yIChJbnRlZ2VyIG51bWJlciA6IGludGVnZXJzKSB7CiAgICAgICAgICAgIC8vIGhlYWRTZXQgaXMgbm90IGluY2x1c2l2ZSwgKzEgaXMgdG8gbWFrZSBpdCBpbmNsdWRlIHRoZSBleGFjdCBzdW0KICAgICAgICAgICAgaW50IGRpZmYgPSB0aHJlc2hvbGQgLSBudW1iZXIgKyAxOwogICAgICAgICAgICBTZXQ8SW50ZWdlcj4gaW50ZWdlckludGVnZXJTb3J0ZWRNYXAgPSBzb3J0ZWRTZXQuaGVhZFNldChkaWZmKTsKCiAgICAgICAgICAgIE1hcC5FbnRyeTxJbnRlZ2VyLCBTZXQ8SW50ZWdlcj4+IGludGVnZXJTZXRQYWlyID0gbmV3IEFic3RyYWN0TWFwLlNpbXBsZUVudHJ5PEludGVnZXIsIFNldDxJbnRlZ2VyPj4obnVtYmVyLCBpbnRlZ2VySW50ZWdlclNvcnRlZE1hcCk7CiAgICAgICAgICAgIHJlc3VsdC5hZGQoaW50ZWdlclNldFBhaXIpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzdWx0OwogICAgfQoKCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgSW50ZWdlcltdIGludGVnZXJzID0gezQsIDEsIDUsIDIsIDMsIC0xLCA2LH07CiAgICAgICAgSW50ZWdlciB0aHJlc2hvbGQgPSA0OwogICAgICAgIExpc3Q8TWFwLkVudHJ5PEludGVnZXIsIFNldDxJbnRlZ2VyPj4+IHNvbHV0aW9uID0gbmV3IEZpbmRQYWlyc1VuZGVyVGhyZXNob2xkKCkuc29sdmUoaW50ZWdlcnMsIHRocmVzaG9sZCk7CiAgICAgICAgZm9yIChNYXAuRW50cnk8SW50ZWdlciwgU2V0PEludGVnZXI+PiBlbnRyeSA6IHNvbHV0aW9uKSB7CiAgICAgICAgICAgIEludGVnZXIgZmlyc3QgPSBlbnRyeS5nZXRLZXkoKTsKICAgICAgICAgICAgZm9yIChJbnRlZ2VyIHNlY29uZCA6IGVudHJ5LmdldFZhbHVlKCkpIHsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoIigiICsgZmlyc3QgKyAiLCAiICsgc2Vjb25kICsgIiksICIpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKfQo=