<< problem 197 - Investigating the behaviour of a recursively ... | Squarefree Binomial Coefficients - problem 203 >> |

# Problem 201: Subsets with a unique sum

(see projecteuler.net/problem=201)

For any set A of numbers, let sum(A) be the sum of the elements of A.

Consider the set B = {1,3,6,8,10,11}.

There are 20 subsets of B containing three elements, and their sums are:

sum({1,3,6}) = 10,

sum({1,3,8}) = 12,

sum({1,3,10}) = 14,

sum({1,3,11}) = 15,

sum({1,6,8}) = 15,

sum({1,6,10}) = 17,

sum({1,6,11}) = 18,

sum({1,8,10}) = 19,

sum({1,8,11}) = 20,

sum({1,10,11}) = 22,

sum({3,6,8}) = 17,

sum({3,6,10}) = 19,

sum({3,6,11}) = 20,

sum({3,8,10}) = 21,

sum({3,8,11}) = 22,

sum({3,10,11}) = 24,

sum({6,8,10}) = 24,

sum({6,8,11}) = 25,

sum({6,10,11}) = 27,

sum({8,10,11}) = 29.

Some of these sums occur more than once, others are unique.

For a set A, let U(A,k) be the set of unique sums of k-element subsets of A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and sum(U(B,3)) = 156.

Now consider the 100-element set S = {1^2, 2^2, ... , 100^2}.

S has 100891344545564193334812497256 50-element subsets.

Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of S, i.e. find sum(U(S,50)).

# My Algorithm

Despite the high number of 50-elements subsets there is only a small number of possible sums:

\sum_{i=50..100}{i^2} < 300000

That means I have to check about 300000 numbers whether they can be reached by adding 50 square numbers.

To be more specific, I have to check whether there is exactly one way to reach them by adding 50 squares.

The initial step is to generate all subsets of size 0 - there is only the empty set which is unique and has sum 0.

Then I process all numbers 1^2, 2^2, ..., 100^2 and do the following:

- iterate over all subset sizes, beginning with the highest (50)

- pick each valid subset (`reachable[] = true`

) and add the current number

- check if the subset without the current number was unique (see `duplicates[] = false`

) and whether adding the current number produces a unique sum, too.

Finally, add all unique sums of size 50.

My first prototype was based on `std::map`

but extremely slow and memory consuming.

The published code works with highly efficient bit masks (`std::vector<bool>`

).

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <vector>
int main()
{
unsigned int maxSet = 100;
unsigned int choose = 50;
std::cin >> maxSet >> choose;
// all squares
std::vector<unsigned int> values;
for (unsigned int i = 1; i <= maxSet; i++)
values.push_back(i*i);
std::vector<std::vector<bool>> reachable (choose + 1);
std::vector<std::vector<bool>> duplicates(choose + 1);
for (size_t i = 0; i < reachable.size(); i++)
{
// heuristic to allocate only as much memory as needed
size_t maxSize = maxSet*maxSet * i + 1;
if (maxSize > 300000) // somewhat below 300000 different sums
maxSize = 300000;
reachable [i].resize(maxSize, false);
duplicates[i].resize(maxSize, false);
}
// the empty set is always possible
reachable[0][0] = true;
// for each square ...
for (auto add : values)
{
// try to append it to any valid set
for (unsigned int numElements = choose; numElements > 0; numElements--)
{
// try every valid sum
for (size_t sum = 0; sum < reachable[numElements - 1].size(); sum++)
{
// sum must be possible
if (!reachable[numElements - 1][sum])
continue;
// append number to previous sum
auto current = add + sum;
// "sum" was a duplicate or "current" already exists ?
if (duplicates[numElements - 1][sum] ||
reachable[numElements][current])
{
// new sum is reachable but invalid
reachable [numElements][current] = true;
duplicates[numElements][current] = true;
}
else
{
// yes, new unique sum
reachable[numElements][current] = true;
}
}
}
}
// count all unique sums
unsigned int result = 0;
for (size_t sum = 0; sum < reachable[choose].size(); sum++)
if (reachable[choose][sum] && !duplicates[choose][sum])
result += sum;
std::cout << result << std::endl;
return 0;
}

This solution contains 9 empty lines, 12 comments and 2 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "100 10" | ./201`

Output:

*Note:* the original problem's input `100 50`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in 1.5 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

Peak memory usage was about 5 MByte.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

July 2, 2017 submitted solution

July 2, 2017 added comments

# Difficulty

Project Euler ranks this problem at **65%** (out of 100%).

# Links

projecteuler.net/thread=201 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 197 - Investigating the behaviour of a recursively ... | Squarefree Binomial Coefficients - problem 203 >> |