import java.util.*;
public class GSum2 {
    static boolean findSum(int[] data,int target_sum,int pos,List<Integer> list) {
        if(pos >= data.length) return target_sum == 0;
        // Does the answer include the data at position pos
        boolean b = findSum(data, target_sum - data[pos], pos+1,list);
        if(b) { list.add(data[pos]); return true; }
        // Does the answer NOT include the data at position pos
        return findSum(data, target_sum, pos + 1,list);
    }
    public static List<Integer> findSum(int[] data,int target_sum) {
        List<Integer> list = new ArrayList<>();
        findSum(data,target_sum,0,list);
        return list;
    }

    public static void test(int[] data, int target_sum, boolean found) {
        List<Integer> li = findSum(data, target_sum);
        int sum = 0;
        for(Integer a : li) sum += a;
        if(found) {
            assert sum == target_sum;
            System.out.printf("sum %s == %d%n",li,target_sum);
        } else {
            assert li.size() == 0;
        }
    }

    public static void main(String[] args) {
        test(new int[]{3,5,7,9},16,true);
        test(new int[]{3,5,7,9},-1,false);
        test(new int[]{3,5,7,9,13},21,true);
    }
}