Блог пользователя mehrshadlotfi

How many subsets have the sum of x?
Автор mehrshadlotfi, история, 9 лет назад, По-английски

Consider we have a set of n numbers, and we want to calculate the number of subsets in which the addition of all elements equal to x.

Input first line has n, x and the next line contains n numbers of our set. In the output we have to calculate the number of subsets that have total sum of elements equal to x.

INPUT 4 3 -1 2 4 2

OUTPUT 2

  • Проголосовать: нравится
  • -20
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

constrains ?

→ Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

This is a classic dp problem ( count number of ways ) .

a simple solution is iether add the current element of the set to the sum or leave it , i suppose that The constrains are not important .

int fun(int sum,int step)
{
   if(step==n) return sum==x;
   if(memo[sum][step]!=-1) return memo[sum][step];
   int ans=0;
   ans+=fun(sum,step+1);
   ans+=fun(sum+a[step],step+1);
   return memo[sum][step]=ans;
}

of course memo is filled with -1 .

I sudjest that you learn Dynamic Programming first .

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Nice solution. Thanx.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If the set contains negative values is better to use map rather than a simple array .

      → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry . i am a beginner. why are you not using conditions like the element is greater than the sum or not and then including it?

    if(a[n-1]>sum)
{
dont include
}
else
{
include
}
    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how to initialize negative value memo if decleare a map

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Eather check if map value was inserted, or even beter solution is to keep an array and instead of-1 put a value that will never appear as an answer like if the minimum possible value is -1000,initialize your array with -1001.

      → Ответить