本文共 644 字，大约阅读时间需要 2 分钟。

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.

-----------------------------------------------------------------------------------------------

Maximum sum can be = N*(N+1) / 2 for any subset considered. 
Hence put S = (N*(N+1) / 2) in subset sum problem. 

i.e dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]; // check for cases when j-a[i] < 0. 
iterate i from 1 to N and j from 0 to S. 
ans = 0; 
again iterate from j = 0 to S and check if j is prime, and if j is prime then 
ans = ans + dp[N][j]; 

output ans.

Dynamic Programming is often associated with the number of blank blank....

转载地址：http://ywboi.baihongyu.com/