import java.util.Arrays;

/**
 * @author /u/Philboyd_Studge on 12/16/2015.
 */
public class Advent17 {

    public static int count(int total, int[] array) {
        if (total == 0) return 1;
        if (array.length == 0) return 0;
        if (total < 0) return 0;

        int test = array[0];
        array = Arrays.copyOfRange(array, 1, array.length);
        return count(total - test, array) + count(total, array);
    }

    public static int count(int total, int[] array, int number) {
        if (total == 0 && number == 0) return 1;
        if (array.length == 0) return 0;
        if (total < 0) return 0;

        int test = array[0];
        array = Arrays.copyOfRange(array, 1, array.length);
        return count(total - test, array, number - 1) + count(total, array, number);
    }
    public static void main(String[] args) {

        final int TARGET = 150;
        int[] containers = {43, 3, 4, 10, 21, 44, 4, 6, 47, 41, 34, 17, 17,
                            44, 36, 31, 46, 9, 27, 38};

        System.out.printf("Part 1 : %d%n", count(TARGET, containers));

        int min = 0;
        int combos = 0;
        while (combos == 0) {
            combos = count(TARGET, containers, min++);
        }

        System.out.printf("Part 2 : %d%n" , combos);


    }
}