Subsets such that the sum of numbers in the subset is a prime number.

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.

Algorithm :

1) Generate all subsets using 0-1 Knapsack i.e this helps determine the number of ways it is possible get the value i, input ranging from 1 to n. The general complexity of 0-1 Knapsack is O(nK) where K is the sum of all elements in the vector. Since there are numbers ranging from 1 to n i.e sum is n(n-1)/2. The overall complexity becomes O(n^3)

For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. Recurrence for the same is:
Sum[0,0]=True
For S=1 to L do Sum[0, S]= False
For k=1 to n do
     For S = 0 to L do
           Sum[k, S] = Sum[k-1, S] or Sum[k-1, S - x(k)]

2) Iterate all subsets which are prime. O(K)

public class PrimeSubset {

	private static int[] primes;
	private static int count = 0;

	public static void main(String[] args) {
		findPrimeSubsets(100);
	}

	public static void findPrimeSubsets(int N) {
		int sum = (N * (N + 1)) / 2;
		primes = new int[sum];
		primes[0] = 2;
		primes[1] = 3;
		count = 2;

		boolean[][] matrix = new boolean[N + 1][sum + 1];

		for (int i = 0; i <= N; i++) {
			matrix[i][0] = true;
		}

		for (int j = 1; j <= sum; j++) {
			matrix[0][j] = false;
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= sum; j++) {
				matrix[i][j] = matrix[i - 1][j]
						|| ((i <= j) && (matrix[i - 1][j - i]));
			}
		}

		for (int i = 2; i <= sum; i++) {
			if (matrix[N][i] && isPrime(i)) {
				System.out.println(i);
				primes[count] = i;
				++count;
			}
		}
	}

	public static boolean isPrime(int n) {

		if (n <= 1) {
			return false;
		} else if (n == 2 || n == 3) {
			return true;
		}
		int sqrt = (int) Math.ceil(Math.sqrt(n));
		boolean prime = true;
		for (int k = 0; k < count && primes[k] <= sqrt; k++) {
			if (n % primes[k] == 0) {
				prime = false;
				break;
			}
		}
		return prime;
	}
}