Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### train55's blog

By train55, history, 2 months ago, ,

Can anyone give me the solution or send me the solution to this problem: I have an integer s I want to know the number of ways to express s as a sum of different elements from the array a[].(without repetition). Thank you!!

• -20

 » 2 months ago, # |   +8 constrains?
 » 2 months ago, # |   0 Maybe this is what you need, link
•  » » 2 months ago, # ^ |   0 He said no repetitions. In that case, try all subsets of a[ ]. Unless the problem limits the values of s and values in the array, I'm not aware of any polynomial-time algorithm.
•  » » » 2 months ago, # ^ |   0 So where is a way repeated in the solution(link)? Like if as given $s$=$4$ and $a$ = {1,2,3}.$ways$: 1.{1,1,1,1} 2.{1,1,2} 3.{1,3} 4.{2,2} These are the $4$ possible ways.right?
•  » » » » 2 months ago, # ^ |   0 In the first way, you're using 1 4 times. I think that's what the OP meant by repetition.
 » 2 months ago, # |   +3 This is just basic knapsack dp. Essentially you do the coin change dp solution mentioned above except iterate through the array backwards to avoid repetition.