Count Subsets with a Given Sum

/*
 * Problem : Count subsets.
 * Input   : n, n integers, then k.
 * Output  : The count.
 * Approach: Take or skip.
 * Time    : O(2^n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: count(index, remaining) = the number of ways to choose from a[index..] so that the sum is "remaining".
        static long count(int[] a, int index, long remaining) {
            // Step 2: Base case. No more elements. There is exactly one way if nothing is left to add: the empty choice.
            if (index == a.length) {
                return remaining == 0 ? 1 : 0;
            }

            // Step 3: Two choices for this element: skip it, or take it.
            return count(a, index + 1, remaining) + count(a, index + 1, remaining - a[index]);
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(int[] a, int k) {
        return count(a, 0, k);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}