On thinking a bit more it seems that the problem is roughly equivalent with calculating the sum of each item of the power set, which is O(2**N), and I see no obvious way to reduce that to O(N**3).

It's obviously not the best algorithm, and I rushed the implementation.

use strict;
use warnings;

use Algorithm::Loops qw( NextPermuteNum );
use List::Util       qw( sum );

my @nums = @ARGV;

my $sum  = sum @nums;
my @best = @nums;
my $best;
@nums = sort { $a <=> $b } @nums;
do {
   my $p = $sum;
   my $q = 0;
   for my $i (0..$#nums) {
      my $x = $nums[$i];
      $p -= $x;
      $q += $x;
      my $diff = abs($p-$q);
      if (!defined($best) || $best > $diff) {
         $best = $diff;
         @best = (
            [ @nums[ 0    .. $i     ] ],
            [ @nums[ $i+1 .. $#nums ] ],
         );
      }
   }
} while ( NextPermuteNum(@nums) );

my @p = @{ $best[0] };  print(sum(@p), ": ", join('+', @p), "\n");
my @q = @{ $best[1] };  print(sum(@q), ": ", join('+', @q), "\n");
[download]

>perl script.pl 8 14 32 29
40: 8+32
43: 14+29

>perl script.pl 7 10 12 15 40
44: 7+10+12+15
40: 40
[download]

I'm not clear on the complexity of NextPermuteNum — I have a cold that is making me very tired — so maybe my analysis is wrong.

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)