Solution to Subset Sum Problem

What is subset sum problem?
Subset Sum Problem is this: given a set of integers, does there exist a subset of those integers whose sum is zero? It is a famous NP-complete problem.

How is my solution?
My solution is optimized for huge inputs. It can solve the inputs that containing almost unlimited random numbers in seconds. Specifically, it requires that arbitrary subset sums of the input are in range (-2^31,2^31 ), and the input is randomized enough so that the solutions are not too sparse.



What makes the solution so fast?
I use an original well-designed algorithm to deal with the huge inputs. It combines dynamic programming and backtracking based on modular arithmetic. It generates some tables containing remainders by dynamic programming, which help reject the hopeless partial solutions during backtracking.

What is the algorithm?

You can view my document(if you fail to open it, please let me know). You should know some basic algorithm about dynamic programming and backtracking. Furthermore, some knowledge about modular arithmetic is necessary.

Can I read the program?
You can read the SML Program. It is commented.
A sample output:

==================== Test Suit =========================
#1 - Simple numbers.
Numbers:
32 25 ~10 2 52 ~43 23 ~1
--------------------------------------------------------
Searching... Solution:
~10 2 52 ~43 ~1
========================================================
#2 - Simple numbers (no solution).
Numbers:
32 25 ~10 2 52 ~43 23
--------------------------------------------------------
Searching... Solution:
None
========================================================
#3 - Powers base 2.
Numbers:
~33554431 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131
072 262144 524288 1048576 2097152 4194304 8388608 16777216
--------------------------------------------------------
Searching... Solution:
~33554431 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131
072 262144 524288 1048576 2097152 4194304 8388608 16777216
========================================================
#4 - Numbers that have unique solution.
Numbers:
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 ~3 7 12 17 22 27 32 37 42 47 52 57
62 67 72 77 2
--------------------------------------------------------
Searching... Solution:
1 ~3 2
========================================================
#5 - 20 random numbers in range (-1 000, 1 000).
Numbers:
930 ~444 883 550 ~592 ~729 ~724 ~353 ~207 50 450 ~346 650 807 164 ~601 516 613 ~
64 ~840
--------------------------------------------------------
Searching... Solution:
~207 ~346 650 807 ~64 ~840
========================================================
#6 - 50 random numbers in range (-100 000, 100 000).
Numbers:
3362 780 ~699 ~2557 6885 ~6765 ~2835 4498 906 2858 7498 9698 1479 ~6873 7366 ~32
19 ~1527 ~7973 4572 ~3298 ~1286 8746 1346 3374 6178 9150 ~8923 ~7838 ~7430 ~4401
 ~250 ~8803 5066 9567 ~9058 4219 5096 ~3068 ~3618 3114 ~7686 ~955 ~4734 ~6412 ~6
686 ~8496 9208 6112 ~5629 3807
--------------------------------------------------------
Searching... Solution:
9567 ~9058 ~3068 3114 ~955 ~6412 ~6686 9208 6112 ~5629 3807
========================================================
#7 - 200 random numbers in range (-10 000 000, 10 000 000).
Numbers:
4979531 319511 ~2297074 ~3585090 2534948 ~5925114 ~9501339 8220858 8823355 ~9825
167 1078174 4258096 5238783 ~493643 5127085 9323254 ~850635 ~9113546 3765460 ~34
39886 ~1491035 528012 62453 4536359 5194374 7862852 2299323 ~7964350 ~7380840 ~3
199800 ~1349801 ~8282191 2671568 3735368 ~3037695 7598268 3391298 2221240 932757
2 9429998 ~4363286 ~1196766 ~3241301 ~6560367 ~6647673 ~8618047 9412368 7290179
~6925612 1901469 2179158 ~2272141 ~2684262 4981744 ~7886281 ~2417402 ~1355295 74
32545 ~7175025 ~9100195 9399542 9734031 7262764 1131150 3276597 ~2905782 ~146353
2 ~6541638 ~3423339 ~1296697 ~7757890 3390777 ~2995532 ~2985791 8671937 2409861
~5472808 5817461 7772286 ~1554515 ~7632906 ~5584596 ~4303313 ~25344 ~105322 1023
708 3286262 5764296 9306855 969441 ~8769920 ~8021661 8427141 ~3916606 ~1448947 ~
2527909 7104144 ~6794187 489037 9691900 5954732 ~4789902 3172888 2256159 ~6522 ~
4192449 4830996 ~5010317 ~9983927 9647442 6184890 ~5699398 1055415 899167 887954
7 ~3226647 3706351 2352564 ~9934559 ~2967675 8473463 ~4609589 ~119826 768213 480
15 4316976 6068664 9131729 247240 ~5624326 ~5072593 ~4435832 ~3440 ~7991130 2724
819 4218212 ~3867682 8794088 1474300 3131387 6728811 6262943 ~1940171 ~8864013 ~
7069496 ~3604513 ~4084278 ~4534702 9100367 6237190 ~7393178 260194 623415 ~92015
3 ~4534828 2698464 ~8043726 ~1990230 ~2137761 6106226 ~6241242 ~8489942 7821096
6874445 ~3205950 2649120 1383886 ~1994423 ~3305535 ~3468488 ~7263058 ~8670966 ~7
47405 5560590 ~8679072 ~4876582 8971009 66794 ~7268443 7225592 7942745 ~2167877
~8509421 ~6185829 ~3185863 ~2058560 ~8387872 1330639 2794240 6068175 9332315 181
5994 ~8020338 ~7318425 6864752 ~868998 ~9169799 ~6022036 3767361 ~2523527
--------------------------------------------------------
Searching... Solution:
7862852 2299323 ~7964350 ~3199800 2671568 ~3037695 7598268 3391298 9327572 ~4363
286 ~1196766 ~3241301 ~6560367 ~6647673 ~8618047 9412368 7290179 ~6925612 190146
9
========================================================