Alice and Bob buy crackers

Alice and Bob want to buy firecrackers. There are $N$ types of firecrackers available in the market with an ID $i$ ranging from $1$ to $N$. The cost of each firecracker is $C_i$. Each firecracker can be bought at most once. Bob's father allows him to spend all the money in any way but his only condition is that Alice and Bob receive equal amounts of money.

Your task is to determine the number of different amounts of money both can receive from Bob's father. You are given the cost of all crackers and the money according to the condition provided. 

In other words, let $S$ be a set. For each subset of firecrackers, if the sum of the costs of these firecrackers is even, then add their sum to $S$ and print the size of $S$. Note that the set does not contain equal elements.

Example:

Input:  3
2 5 8
Output: 3

Approach

Java

public class AliceAndBoyCrackers {
    public static void main(String[] args) {

        int n = 3;
        int count = 0;
        int arr[] = { 2, 5, 8 };

        boolean match[] = new boolean[n * 1010];
        match[0] = true;
        for (int i = 0; i < n; i++) {
            int a = arr[i];
            boolean match1[] = new boolean[n * 1010];
            for (int j = 0; j < match.length - a; j++) {
                if (match[j]) {

                    if (!match[j + a]) {
                        match1[j + a] = true;
                        if ((j + a) % 2 == 0)
                            count++;
                    }
                }
            }
            for (int j = 0; j < match1.length; j++) {
                if (match[j] || match1[j]) {
                    match[j] = true;
                }
            }
        }

        System.out.println(count);

    }

}