Monday, January 2, 2012

Given a set of numbers [1-N]. 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.
Approach:
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.



No comments:

Post a Comment