### tzc___wk's blog

By tzc___wk, history, 7 weeks ago, ,

You're given $n$ integers $a_1,a_2,\dots,a_n$, you need to count the number of ways to choose some of them (no duplicate) to make the sum equal to $S$. Print the answer in modulo $10^9+7$. How to solve this problem in polynomial time?

• -3

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by juruo_tzc (previous revision, new revision, compare).
 » 7 weeks ago, # |   -14 I think this should work . let's make a dp array where dp[i] = no. of ways to make sum i .Now we don't want to repeat our items so we are going to iterate from the end of sum .For more info watch Errichto DP tutorial 2 . (Well actually I don't remember the exact number but I think it's 2 ) . Code int n; cin>>n; int a[n]; for(int i = 0 ; i < n; ++i) cin>>a[i]; int N; // The sum we want to make . cin>>N; int dp[N+1]; memset(dp , 0 , sizeof dp); dp[0] = 1; sort(a , a + n); for(int i = 0 ; i < n ;++i){ for(int j = N ; j >= a[i] ; --j) dp[j]+=dp[j-a[i]]; } cout<