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
constrains ?
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 .
of course memo is filled with -1 .
I sudjest that you learn Dynamic Programming first .
Nice solution. Thanx.
If the set contains negative values is better to use map rather than a simple array .
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?
how to initialize negative value memo if decleare a map
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.