spoj main72 subset sum

the problem asks to compute sum of distinct subset sums of the given array of integers;

as the range of numbers in the array is 0 to 1000; and the size of arr is 100, we can assume that the number distinct values cannot be more than 1000*100, So complexity wise it is ok to compute all distinct subset sums. for which we can use a set.

https://gist.github.com/dfdad3667ba70be17e08

PS: i got tle for set but made it to ac by using unordered_set

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s