The number of permutations is actually n!, which is why your algorithm doesn't run in polynomial time:

$ time perl foo2.pl 1 2 3 4 5 6 7
14: 1+2+4+7
14: 3+5+6

real    0m0.096s

time perl foo2.pl 1 2 3 4 5 6 7 8
18: 1+2+3+4+8
18: 5+6+7

real    0m0.590s


time perl foo2.pl 1 2 3 4 5 6 7 8 9
22: 1+2+3+4+5+7
23: 6+8+9

real    0m5.766s

$ time perl foo2.pl 1 2 3 4 5 6 7 8 9 10
28: 1+2+3+4+5+6+7
27: 8+9+10

real    0m57.315s

$ time perl foo2.pl 1 2 3 4 5 6 7 8 9 10 11 
33: 1+2+3+4+5+7+11
33: 6+8+9+10

real    11m5.687s
[download]

You can see that there's a (very rough) factor of 10 between each of these runs, which indicates exponential growth.

(Update: added result of last calculation; Second Update: I had some stupid copy&paste errors in the data, which Hue-Bond++ was so friendly to point out. Fixed)