How to make equal subsets of integers?

Question

Suppose I have an array as under

array[] = {14,10,20,4}

This array can be divided into to subsets {14,10} and {20,4} since these two have equal sum.

Another example may be

array[] = {5, 5, 15, 5}

This array can be divided into to subsets {5,5,5} and {15} since these two have equal sum.

But

array[] = {1, 5, 30} 

Cannot be divided into equal sets as they can never be equal.

How can we do so?

My shot

var result = string.Empty;
int highestNumber = input1[0];
int sum = 0;
string set = string.Empty;

foreach (int value in input1) 
    if (value > highestNumber) highestNumber = value;

for (int i = 0; i < input1.Length; i++)
{
    var elements = input1[i];
    if (elements > 0)
    {
        if (elements != highestNumber)
        {
            sum += elements;
            set += "," + elements; 
        }
    }
}

if (sum == highestNumber)
    result = "Yes it can be partitioned" 
else
    result = "No it cannot be";

Console.WriteLine(result);

It does not work for the first one.

How to do this program?

Answer 1

I created a solution based on a array of bits, a bitset, in C# bool[]. Before I show the solution I first had to add some extension methods to this bool[]. These are generic functions and can be used in other solution. It is placed at the bottom of this answer.

As I said it is based on the bitset. The bitset will have the length of the array of numbers which need to be group. The bitset will be filled with zero's and one. Each bit corresponds with one number. So if the array of numbers has 5 elements, the bitset will also have 5 bits.

If a bit is 0, the number is going to be place in group0. If the bit is 1, the number is going to be placed into group1. When both groups have the same sum, the work is done.

This loop is repeated until all combinates are analyzed. The bitset will start with the numeric value op 1 (in case of 5 numbers: 00001). It will increase every iteration (so the next interation will be 00010, then 00011, then 00100, etc.) So changing the bits of the bitset and regrouping the numbers.

Be aware: I create this method with only its functionallity in mind. I did not mind any performance issues. Of course this routine can be made faster (i.e. not create new lists every iterations, etc.) but that would make the code less readable. I tried to make this code as readable as possible.

static public bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
{
    if (numbers == null)
        throw new ArgumentNullException("numbers");

    bool[] groupPerNumber = new bool[](numbers.Count);
    while (true)
    {
        groupPerNumber.Increase(); // Increate the numberic value of the array of bits.
        if (groupPerNumber.IsEmpty()) // If all bits are zero, all iterations have been done.
            break;

        // Create the new groups.
        group0 = new List<int>();
        group1 = new List<int>();

        // Fill the groups. The bit in the groups-array determains in which group a number will be place.
        for (int index = 0; index < numbers.Count; index++)
        {
            int number = numbers[index];
            if (!groupPerNumber[index])
                group0.Add(number);
            else
                group1.Add(number);
        }

        // If both sums are equal, exit.
        if (group0.Sum() == group1.Sum())
            return true;
    }
    group0 = group1 = null;
    return false;
}

Array of boolean Extensions

static public class BoolArrayExtensions
{
    /// <summary>
    /// Treats the bits as a number (like Int32) and increases it with one.
    /// </summary>
    static public void Increase(this bool[] bits)
    {
        for (int i = 0; i < bits.Length; i++)
        {
            if (!bits[i])
            {
                bits[i] = true;
                bits.SetAll(0, i - 1, false);
                return;
            }
            bits[i] = false;
        }
        bits.SetAll(false);
    }

    /// <summary>
    /// Sets the subset of bits from the start position till length with the given value.
    /// </summary>
    static public void SetAll(this bool[] bits, int start, int length, bool value)
    {
        while(length-- > 0)
            bits[start++] = value;
    }

    /// <summary>
    /// Returns true if all bits in the collection are false.
    /// </summary>
    static public bool IsEmpty(this bool[] bits)
    {
        for (int i = 0; i < bits.Length; i++)
            if (bits[i])
                return false;
        return true;
    }
}

EDIT

I created another solution like this and placed it at codereview. It is basically the same function, but this time optimized form speed. Interested? Take a look: https://codereview.stackexchange.com/questions/25980/performance-devide-group-of-numbers-into-two-groups-of-which-the-sums-are-equal

Answer 2

First you can start out with a method to get the combinations for the items in a list. This is most easily solved by creating the combinations for a number and then translating that from numbers to indexes of your collection:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IList<T> source, int n)
{
    return Combinations(source.Count, n)
        .Select(combination => combination.Select(i => source[i]));
}

public static IEnumerable<IEnumerable<int>> Combinations(int n, int p)
{
    //this is logically treated as a stack except that when enumerated it's enumerated as the 
    //reverse of a stack, which is desirable.  There is no efficient way to get the reverse iterator
    //of System.Collections.Stack so easily.  All mutations are to the end of the list.
    var stack = Enumerable.Range(0, p).ToList();

    while (stack[stack.Count - 1] < n)
    {
        //the ToList can be removed if previous sub-sequences won't be iterated 
        //after the outer sequence moves to the next item.
        yield return stack.ToList();
        int lastValue = stack.Pop();

        while (stack.Any() && lastValue + 1 > n - (p - stack.Count))
        {
            lastValue = stack.Pop();
        }

        while (stack.Count < p)
        {
            lastValue += 1;
            stack.Add(lastValue);
        }
    }
}

//simple helper method to get & remove last item from a list
public static T Pop<T>(this List<T> list)
{
    T output = list[list.Count - 1];
    list.RemoveAt(list.Count - 1);
    return output;
}

Using that it's a simple matter to create a method to get all combinations for a set, rather than just combinations of a particular size:

public static IEnumerable<IEnumerable<T>> AllCombinations<T>(this IList<T> source)
{
    IEnumerable<IEnumerable<T>> output = Enumerable.Empty<IEnumerable<T>>();
    for (int i = 1; i < source.Count; i++)
    {
        output = output.Concat(Combinations(source, i));
    }
    return output;
}

Now that we have the ability to get all combinations for the list we can use LINQ to finish the job:

List<int> list = new List<int>() { 5, 5, 15, 5 };

var groups = list.AllCombinations()
    .GroupBy(combination => combination.Sum());

Using that you now have all of the groups of combinations that sum up to the same value.

Answer 3

You want to partition the given int array into 2 partitions where the sums of the partitions are equal.

The approach could be:

1. See if the sum of all items is divisible by 2 (otherwise, cannot be partitioned)
2. Get all subsets of the array
3. Find the subsets where the sum is [sum of all items] / 2

Here's the code:

class Program
{
    static void Main(string[] args)
    {
        var arrays = new int[][] {
            new[]{ 1, 12, 10, 2, 23 },
            new[] {14,10,20,4},
            new[] {5, 5, 15, 5},
            new[] {1, 5, 30}
        };

        foreach (var array in arrays)
        {
            Console.WriteLine(String.Format("Results for {0}:", string.Join(",", array)));
            IEnumerable<IEnumerable<int>> partitions = Partition(array);
            if (!partitions.Any()) 
                Console.WriteLine("Cannot be partitioned.");
            else
                foreach (var item in partitions)
                {
                    Console.WriteLine(string.Join(",", item));
                }
            Console.WriteLine();
        }

        Console.ReadKey();
    }

    static IEnumerable<IEnumerable<int>> Partition(int[] array)
    {
        var sum = array.Sum();
        if ((sum % 2) == 1) return Enumerable.Empty<IEnumerable<int>>();

        return Subsequences(array).Where(ss => ss.Sum(item => item) == (sum / 2));
    }

    // http://stackoverflow.com/a/3750709/201088
    private static IEnumerable<IEnumerable<T>> Subsequences<T>(IEnumerable<T> source)
    {
        if (source.Any())
        {
            foreach (var comb in Subsequences(source.Skip(1)))
            {
                yield return comb;
                yield return source.Take(1).Concat(comb);
            }
        }
        else
        {
            yield return Enumerable.Empty<T>();
        }
    }
}

Output:

Results for 1,12,10,2,23:
12,10,2
1,23

Results for 14,10,20,4:
14,10
20,4

Results for 5,5,15,5:
15
5,5,5

Results for 1,5,30:
Cannot be partitioned.

Answer 4

Calculate the sum of your array and divide it by two. Now you know the desired norm (summed value) of your sets.

Depending on your performance requirements and the expected size you can use a simple backtracking algorythm to walk down all possibilities. Since you know the exact sum which a set must have, you can limit the search significantly.