train55's blog

By train55, history, 4 years ago, In English

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

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

constrains?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe this is what you need, link

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In the first way, you're using 1 4 times. I think that's what the OP meant by repetition.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.