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!!

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

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!!

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2020 23:51:45 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

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 ofsand values in the array, I'm not aware of anypolynomial-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

14 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.