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

Problem

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.

Solution 

Method 1 - Using DP

Maximum sum can be = N*(N+1) / 2 for any subset considered, as numbers are from 1 to N.

Hence put S = (N*(N+1) / 2) in subset sum problem.

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)]

Then for all the subsets Sum Si which can be generated with numbers from 1 to N, check if those are Prime.

Java code

public static void findPrimeSubsets() {
 int N = 200;
 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++) {
  //for (int i=primes[k]; i<=sqrt; ++i) {
  if (n%primes[k] == 0) {
   prime = false;
   break;
  }
  // }
 }

 return prime;
}

References 

• http://karmaandcoding.blogspot.in/2012/01/given-set-of-numbers-1-n-subsets-such.html