Kaido has a precious chest with a number written on it.

Kaido.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Kaido has a precious chest with a number written on it. The chest has two keyholes.
 * He also has a keychain with n keys on it. A number of labels each key.
 * To unlock this chest, we need to insert two of his keys such as the labels on them sum up to the number written on the chest.
 * Can you help to unlock this chest ?
 * <p/>
 * <b>INPUT: </b>
 * <b>Line 1: </b>
 * target, the integer written on the chest.
 * <p/>
 * <b>Line 2: </b>
 * An integer N representing the size of the chain.
 * <p/>
 * <b>Line 3: </b>
 * Key[], an array of size N representing the numbers on kaido's keychain (keys[i] = the number written on the i-th key).
 * <p/>
 * <b>OUTPUT: </b>
 * The index of the keys that could unlock the chest.
 * You may assume that each input would have <b>exactly one solution</b>.
 * <p/>
 * <b>CONSTRAINTS: </b>
 * 2 <= N <= 10000
 * -1000000 <= keys[i] <= 1000000, 0 <= i <= N
 * -1000000 <= target <= 1000000
 * <p/>
 * <b>EXAMPLE: </b>
 * <table border="0">
 *   <tr>
 *     <td> Input </td> <td> Output</td>
 *   </tr>
 *   <tr>
 *     <td> 5 </td> <td> 0 3 </td>
 *   </tr>
 *   <tr>
 *     <td> 4 </td>
 *   </tr>
 *   <tr>
 *     <td> 3 8 11 2 </td>
 *   </tr>
 * </table>
 */
public class Kaido {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int target = in.nextInt();
        int n = in.nextInt();

        int sum = 0;
        int[] keys = new int[n];
        List<Integer> sumPositions = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int key = in.nextInt();

            keys[i] = key;
            if (sum + key <= target) { // incremental sum
                sumPositions.add(i);
                sum += key;
            }
        }

        if (sum == target) {
            StringBuilder result = new StringBuilder();
            for (Integer sumPosition : sumPositions) {
                result.append(sumPosition).append(" ");
            }
            result.deleteCharAt(result.length() - 1); // last space

            System.out.println(result);
        } else {
            // direct sum
            found_loop:
            for (int idx = 0; idx < keys.length; idx++) {
                int key = keys[idx];

                for (int jdx = 0; jdx < n; jdx++) {
                    if (idx == jdx) {
                        continue;
                    }

                    if (key + keys[jdx] == target) {
                        System.out.println(idx + " " + jdx);
                        break found_loop;
                    }
                }
            }
        }
    }
}