Split the array into two to find the best solution in getting equal or nearly equal sum of integers

Question

I need to solve a problem in which I need to split arrays into two sub-arrays such that the sum of their weights will be equal or "nearly equal".

Explanation

If I have an array [1,2,3,4,5] so I can possibly make two subsets of [1,2,4] = 7 and [3,5] = 8 OR [2,5] = 7 and [1,3,4] = 8.

I have done that part but by dry run i got to know that if i have even number of digits in the set of array then it always gives me wrong answers. This program only works for odd number of digits. What am i missing?

using System.IO;
using System;

class Program
{
    static void Main()
    {
            int[] a = {1,2,3,4};
            int t;
            Console.WriteLine("Original array :");
            foreach (int aa in a)
                Console.Write(aa + " ");
            for (int p = 0; p <= a.Length - 2; p++)
            {
                for (int i = 0; i <= a.Length - 2; i++)
                {
                    if (a[i] > a[i + 1])
                    {
                        t = a[i + 1];
                        a[i + 1] = a[i];
                        a[i] = t;
                    }
                }
            }
            Console.WriteLine("\n" + "Sorted array :");
            foreach (int aa in a)
                Console.Write(aa + " ");
            Console.Write("\n");
         //   int[] arr = new int[5] { 99, 95, 93, 89, 87 };
            int z, max, min, n;
            // size of the array
            n = 4;
            max = a[0];
            min = a[0];
            for (z = 1; z < n; z++)
            {
                if (a[z] > max)
                {
                    max = a[z];
                }
                if (a[z] < min)
                {
                    min = a[z];
                }
            }
            Console.Write("Maximum element = {0}\n", max);
            Console.Write("Minimum element = {0}\n\n", min);
            int e = 0;
            int f = 0;
            int g = 0;
            for(int i = 0; i < n; i++)
            {
                g = f - e;
                int mm = max - min; 
                {
                if(g > mm)
                {
                    e += a[i]; 
                }
                else if(g < mm)
                {
                    f += a[i]; 
                }
                }
                min++;
            }
            Console.Write("The possible solution is:\n ");
            Console.Write("First array = {0}\n", e);
            Console.Write("Second array = {0}\n\n", f); 
            Console.ReadLine();
        }
    }

Answer 1

Here's a code snippet that might help:

var arr = new[] { 1, 2, 3, 4 };
var lst1 = new List<int>();
var lst2 = new List<int>();
var div = Math.DivRem(arr.Sum(), 2, out _);

foreach (var i in arr.OrderByDescending(x => x))
{
    if (lst1.Sum() + i <= div)
        lst1.Add(i);
    else
        lst2.Add(i);
}

Console.WriteLine(string.Join(", ", lst1.OrderBy(x => x)));
Console.WriteLine(string.Join(", ", lst2.OrderBy(x => x)));

Some outputs of:

---

{ 1, 2, 3, 4 }

1, 4
2, 3

---

{ 1, 2, 3, 4, 5 }

2, 5
1, 3, 4

---

{ 1, 2, 3, 4, 5, 6 }

4, 6
1, 2, 3, 5

---

So we iterated through the source array (arr) in a descending order to add numbers into lst1 if the sum of it's contents still less than or equal to the quotient of dividing the sum of the main array by 2, otherwise we add them (the numbers) into lst2 where the sum of it's numbers is equal or nearly equal to the mentioned quotient.

As a result, you have two lists where the sum of their contents are equal or nearly equal.

Answer 2

Below code will split array into 2 with equal sum or least difference in sum.
Apologies for lengthy solution, but it works perfectly for all combinations of odd and even.

Explicit names of variables and functions will help you to understand the logic.

using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    public static void Main(string[] input)
    {
        int[] a = {1, 2, 9, 26, 3, 4, 12, 7, 5};
        int t;

        Console.WriteLine("Original array :" + string.Join(", ", a));       

        for (int p = 0; p <= a.Length - 2; p++)
        {
            for (int i = 0; i <= a.Length - 2; i++)
            {
                if (a[i] > a[i + 1])
                {
                    t = a[i + 1];
                    a[i + 1] = a[i];
                    a[i] = t;
                }
            }
        }


        Console.WriteLine("\n\nSorted array :" + string.Join(", ", a));


        // Newly added code starts 
        int[] sortedArray = a;

        List<int> array1 = new List<int>();
        List<int> array2 = new List<int>();

        for (int index = sortedArray.Length-1 ; index >=0 ; index-- )
        {
            if (array1.Sum() < array2.Sum())
            {
                array1.Add(sortedArray[index]);
            }
            else if (array1.Sum() > array2.Sum())
            {
                array2.Add(sortedArray[index]);
            }
            else
            {
                array1.Add(sortedArray[index]);
            }
        }       

        BalanceArray(array1, array2);


        array1.Sort();
        array2.Sort();

        Console.WriteLine("\n\nArray1 { " + string.Join(", ", array1) + " }\tSum => " + array1.Sum());
        Console.WriteLine("\n\nArray2 { " + string.Join(", ", array2) + " }\tSum => " + array2.Sum());

    }

    private static void BalanceArray(List<int> array1, List<int> array2)
    {       
        int sumOfArray1 = array1.Sum();
        int sumOfArray2= array2.Sum();

        int difference = (sumOfArray1 < sumOfArray2) ?  sumOfArray2- sumOfArray1 : sumOfArray1 - sumOfArray2;

        if ( sumOfArray1 < sumOfArray2 )
        {
            SwapNumber(array2, array1, difference);         
        }
        else if ( sumOfArray1 > sumOfArray2 )
        {
            SwapNumber(array1, array2, difference);         
        }       
    }

    private static void SwapNumber(List<int> biggerArray,List<int> smallerArray, int difference)
    {
        //Console.Write("\n Difference :" + difference);        
        int expectedDifference = difference /2;
        //Console.Write("\n Expected Difference :" + expectedDifference );

        int lowerNoToSwap = 0;
        int higherNoToSwap = 0;
        for(int i=0; i < biggerArray.Count(); i++ )
        {
            if(biggerArray[i] <= expectedDifference)
            {
                lowerNoToSwap =  biggerArray[i];
            }
            else if(biggerArray[i] > expectedDifference)
            {
                higherNoToSwap = biggerArray[i];
                break;              
            }
        }

        if(lowerNoToSwap <= higherNoToSwap)
        {
            bool swapLower = (expectedDifference - lowerNoToSwap) < (higherNoToSwap - expectedDifference) ? true : false;

            int numberToSwap =  swapLower ? lowerNoToSwap : higherNoToSwap;

            if(numberToSwap != 0)
            {
                smallerArray.Add(numberToSwap);
                smallerArray.Sort();
                biggerArray.Remove(numberToSwap);
            }
        }   
    }
}

Example 1

Original array :1, 2, 3, 4


Sorted array :1, 2, 3, 4


before Array1 { 4, 1 }    Sum => 5


before Array2 { 3, 2 }    Sum => 5


Array1 { 1, 4 }    Sum => 5


Array2 { 2, 3 }    Sum => 5

Example 2

Original array :1, 2, 3, 4, 5


Sorted array :1, 2, 3, 4, 5


Array1 { 3, 5 }    Sum => 8


Array2 { 1, 2, 4 }    Sum => 7

Example 3

Original array :1, 2, 9, 26, 3, 4, 12, 7, 5


Sorted array :1, 2, 3, 4, 5, 7, 9, 12, 26


Array1 { 1, 3, 5, 26 }        Sum => 35


Array2 { 2, 4, 7, 9, 12 }        Sum => 34