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

Problem

Solution

See also