mehrshadlotfi's blog

By mehrshadlotfi, history, 8 years ago, In English

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

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

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

constrains ?

»
8 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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 .

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Nice solution. Thanx.

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

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

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

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to initialize negative value memo if decleare a map

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

      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.