tzc___wk's blog

By tzc___wk, history, 7 weeks ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by juruo_tzc (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

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