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!!
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Name |
---|
constrains?
Maybe this is what you need, link
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.
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?
In the first way, you're using 1 4 times. I think that's what the OP meant by repetition.
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.