Backtracking II: equal division of batches

Suppose that you are given a set of N numbers representing stocks batches: some are positive, others are negative. The batches have the following values:

{15, -3, 4, -1, -16, 5, 14, -13, 7, -6, 2, 1}

Your task is to distribute these batches amongst 3 brothers. However… you need to be fair with all the brothers, hence the total dollar amount has to be exactly the same for all the brothers. First question is: is there a solution for this problem? Second: what is the solution?
There are in general two approaches for solving this problem: dynamic programming or backtracking. The first one requires some constraints in terms of the values of the batches – if the batches for instance contain float numbers I’m pretty sure the dynamic programming won’t work. The second approach is the one shown in the previous blog post, which is backtracking, and to recap, here is the overall structure of backtracking solutions:

Backtracking(Enumeration L, Solution S)
{
//Part 1
If (L is the final enumeration)
Check if S is the best one thus far
//Part 2
For each K such that K is in the neighborhood of S
Backtracking(L+1, K)
}

Now, no question that backtracking also has its limitations, and quite big: this problem for instance becomes a pretty bad Big-O(<some big-n-nasty exponential on N and the number of brothers>), so it will only work for small numbers of N (and small number of brothers), but it does not carry the limitations of dynamic programming, meaning it would work just fine for floating numbers. Now, I’m positive this problem is an NP-Complete problem, but I don’t know how to do the reduction, but if it is an NP-Complete then it is pointless to try to find a general solution for very large N’s (and large number of brothers). But still, it is a good candidate to exemplify backtracking – also, since we’re looking for one solution (not the optimal one) the algorithm might be relatively fast if the problem has a solution. It will (may) take a long time if the instance of the problem does not have a solution.
Now, to the backtracking solution: it is exactly the same structure as above: the L runs thru all the batches. For each batch, add it to every single bucket (each bucket represents one brother), try again recursively for L+1, see if you have a solution, if so stop, otherwise keep going. Remember to revert back whenever you add a batch to a bucket and don’t find a solution (that’s the reason for the little subtraction towards the end of part 2). Btw, the solution for the instance of the problem above is the following:

First, yes, there is a way to equally split the batches. And second, the division is:
Brother 1) 15-3+4-1-13+7-6=3
Brother 2) -16+5+14=3
Brother 3) 2+1=3

Interesting enough, for this particular instance, there is no way to split the batches equally if you only had two brothers… Full code (C#) down below, but first the output from the code as it is:

For 1 brothers:
1. 15-3+4-1-16+5+14-13+7-6+2+1=9
For 2 brothers:
No Solution!
For 3 brothers:
1. 15-3+4-1-13+7-6=3
2. -16+5+14=3
3. 2+1=3
For 4 brothers:
No Solution!
For 5 brothers:
No Solution!

//Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace EqualDivision
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = new int[] { 15, -3, 4, -1, -16, 5, 14, -13, 7, -6, 2, 1 };
            for (int nBuckets = 1; nBuckets <= 5; nBuckets++)
            {
                int[] buckets = new int[nBuckets];
                string[] bucketsExpression = new string[nBuckets];
                for (int i = 0; i < nBuckets; i++)
                {
                    buckets[i] = 0;
                    bucketsExpression[i] = "";
                }
                Console.WriteLine("For {0} brothers:", nBuckets);
                if (!IsThereAnEqualDivision(0, numbers, buckets, bucketsExpression))
                {
                    Console.WriteLine("No Solution!");
                }
                Console.WriteLine();
            }
        }
        static bool IsThereAnEqualDivision(int currentIndex,
                                           int[] numbers,
                                           int[] buckets,
                                           string[] bucketsExpression)
        {
            //Part 1: check whether there is a solution
            if (currentIndex >= numbers.Length)
            {
                bool foundSolution = true;
                for (int i = 0; i < buckets.Length - 1; i++)
                {
                    if (buckets[i] != buckets[i + 1])
                    {
                        foundSolution = false;
                        break;
                    }
                }
                if (foundSolution)
                {
                    for(int i=0;i<bucketsExpression.Length;i++)
                    {
                        Console.WriteLine("{0}. {1}={2}", i+1, bucketsExpression[i], buckets[i]);
                    }
                    return true;
                }
                else
                {
                    return false;
                }
            }
            //Part 2: induction. Add the current number to all the buckets
            for (int i = 0; i < buckets.Length; i++)
            {
                buckets[i] += numbers[currentIndex];
                string savedBucketExpression = bucketsExpression[i];
                if (bucketsExpression[i] == "")
                {
                    bucketsExpression[i] = numbers[currentIndex].ToString();
                }
                else
                {
                    bucketsExpression[i] += ((numbers[currentIndex]>=0)?"+":"") + numbers[currentIndex].ToString();
                }
                if (IsThereAnEqualDivision(currentIndex + 1,
                                          numbers,
                                          buckets,
                                          bucketsExpression))
                {
                    return true;
                }
                buckets[i] -= numbers[currentIndex];
                bucketsExpression[i] = savedBucketExpression;
            }
            return false;
        }
                                          
    }
}