## Monday, May 5, 2014

### 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