Solution: The Partition Problem

using System;
class Program
{
    /// <summary>
    /// Checks if two sub-arrays have equal sum or not.
    /// </summary>
    /// <param name="set">Integer array containing positive numbers only.</param>
    /// <returns>True if two sub-arrays have equal sum, otherwise false.</returns>
    public static bool CanPartition(int[] set)
    {
        int setLength = set.Length;
        int sum = 0;
        foreach (int num in set)
        {
            sum += num;
        }
        // if 'sum' is an odd number, we can't have two subsets with equal sum
        if (sum % 2 != 0)
        {
            return false;
        }
        return CanPartitionRecursive(set, setLength, sum / 2, 0);
    }
    /// <summary>
    /// Checks if two sub-arrays have equal sum or not.
    /// </summary>
    /// <param name="set">Integer array containing positive numbers only.</param>
    /// <param name="setLength">Length of the array.</param>
    /// <param name="sum">Stores sum of the sub-array.</param>
    /// <param name="currentIndex">Index of the sub-array.</param>
    /// <returns>True if two sub-arrays have equal sum, otherwise false.</returns>
    static bool CanPartitionRecursive(int[] set, int setLength, int sum, int currentIndex)
    {
        // base check
        if (sum == 0)
        {
            return true;
        }
        if (setLength == 0 || currentIndex >= setLength)
        {
            return false;
        }
        // recursive call after choosing the number at the currentIndex
        // if the number at currentIndex exceeds the sum, we shouldn't process this
        if (set[currentIndex] <= sum)
        {
            if (CanPartitionRecursive(set, setLength, sum - set[currentIndex], currentIndex + 1))
            {
                return true;
            }
        }
        // recursive call after excluding the number at the currentIndex
        return CanPartitionRecursive(set, setLength, sum, currentIndex + 1);
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        int[] set1 = { 1, 2, 3, 4 };
        Console.WriteLine(CanPartition(set1));
        int[] set2 = { 1, 1, 3, 4, 7 };
        Console.WriteLine(CanPartition(set2));
        int[] set3 = { 2, 3, 4, 6 };
        Console.WriteLine(CanPartition(set3));
    }
}