So... 2**100 is ~ 10**30. If the computer can try one combination in (just for the sake of argument) ~3 micro-secs, it can try ~ 10**13 combinations per annum. So a result may be expected in 10**17 years. Perhaps we should spend more on the hardware ?

Actually, it's not as bad as 2**n. 2**n - 1 is the number of different combinations of n things. However, we have two partitions, A & B, and there is some symmetry, which reduces the number of combinations.

Consider: there are n possible partition A's containing 1 number -- but this is the same arrangement as the n possible partition A's containing n-1 numbers (but with A & B exchanged). So we don't count both of A with 1 number and A with n-1 numbers, and we don't count both A with 2 numbers and A with n-2 numbers, and so on.

The effect of this is to halve the number of possible arrangements[1].

Also: we can discount the 1 possible partition A with all the numbers in it.

Phew. We only have wait half the time we expected. There, that's made a difference :-)

Mind you, we're not taking into account the doubling of processor speed every 18 months or so. Which makes this sort of problem a kind of inverted Xeno's paradox. Let me see, if in 18 months I can buy a machine that will do twice as much work as the one I have: in 36 months time I can have done the same amount of work by waiting 18 months, and starting then with the faster machine. Also, that machine will be cheaper than one I can buy now ! Of course, in 36 months time I will be able to buy an even cheaper machine which is four times as fast. For maximum efficiency, it is clear: I should do nothing, indefinitely !

[1] If n is odd, the number of distinct partitions is exactly 2**(n-1) - 1.
If n is even it's a bit trickier to work out, you have to add (1/2) * (n!/(2*(n/2)!) to that.

Could you discuss the effect of duplicates in the dataset? Is it as simple as making n = no of unique values?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Would you care to elaborate? I admit that I only picked up the "NP complete" that Skeeve mentioned earlier.

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.