# Split the array so that the sum of the numbers on one side of the split equals the sum of the numbers on the other side

I would really appreciate if you can help me to find a better way to do it.

public class SplitArray
{

public SplitArray() { }

public bool CanArrayBeSplit(int[] intArray)
{
foreach(var pair in GeneratePairs(intArray))
{
if (pair.Item1 == pair.Item2)
return true;
}

return false;
}

private List<Tuple<int, int>> GeneratePairs(int[] integerArray)
{
var output = new List<Tuple<int, int>>();
for (int i = 0; i < integerArray.Length -1; i++)
{
output.Add(Tuple.Create(GetSum(0, i+1, integerArray), GetSum(i + 1, integerArray.Length ,integerArray)));
}
return output;
}

private int GetSum(int startIndex, int endIndex , int[] array)
{
int sum = 0;

for (int i = startIndex; i < endIndex; i++)
{
sum += array[i];
}

return sum;
}
}


The solution to this problem is easy, once you know the trick.

The trick, is to calculate the sum of all values then do add/subtract until they match...

This is very different to what you have done, so it does not really make sense to review your algorithm, and then say 'you did it wrong'.

What I will do, is say your code is neat enough, and the logic you have done is visible enough, to make the algorithm clear. Even though it is not the best algorithm, you have implemented it well.

The problems with your algorithm are that you are doing the following:

• you are calculating the sums of each side of the split each time
• you are calculating all possible splits, even if you could identify a successful split sooner
• The Pairs and other classes are overkill for the solution you could have....

So, the following code (on ideone too) makes the 'simple' solution 'obvious'....

public static bool CanArrayBeSplit(int[] intArray) {
int sum = 0;
foreach (int v in intArray) {
sum += v;
}
int left = 0;
int right = sum;
for (int i = 0; left != right && i < intArray.Length; i++) {
left += intArray[i];
right -= intArray[i];
}
return left == right;
}
public static void Main()
{
Console.WriteLine("Testing: " + CanArrayBeSplit(new int[]{1,2,3,4,5,6,7,8,9}));
Console.WriteLine("Testing: " + CanArrayBeSplit(new int[]{1,2,3,4,5,6,7,8,9,45}));

}

• Not the correct solution, will fail in so many cases, like {1,4,4,5,5,11}, which can be dividedinto {1,4,5,5} and {4,11}, but your solution will return false, here's a better solution - geeksforgeeks.org/dynamic-programming-set-18-partition-problem – Mrinal Kamboj Jan 6 '17 at 8:00
• @MrinalKamboj - I believe you have misunderstood the problem being solved. The objective is to "split" the array at a specific index, where the sum of the elements on one side of the index matches the sum on the other side. You are not splitting though, you are instead seeking one subset of the elements that matches the sum of the remainder of the elements, where the subset consists of any elements, not just the left-most elements. My code above solves a simple "split" just fine, but you are right, it is not designed, nor will it work, to solve a non sequential subset. – rolfl Jan 6 '17 at 13:42
• Thanks for the clarification, then I am looking for a different solution – Mrinal Kamboj Jan 9 '17 at 9:07
1. You do not need to re-caclcute sum on every iteration in your GeneratePairs() method. You can simply create two varaibles which would hold the sums of two "sides" of your array. Then on every iteration you can simply add the item value to the first variable and subtract it from second. You can use IEnumerable.Sum() method to get the initial sum value for "right side".
2. I see no reason to keep splitting the array once you have found the split index. You should probably merge CanArrayBeSplit and GeneratePairs methods into one to fix this issue. You can avoid creating pairs this way as well (i think they are not needed here).
3. If you want to actually split an array you should probably store (or return) the split index as well somehow.
left < right && i < intArray.Length