Partition Problem (DP)

README.txt

This problem was asked by Facebook.

Given a multiset of integers, 
return whether it can be partitioned into two subsets whose sums are the same.

For example, given the multiset {15, 5, 20, 10, 35, 15, 10}, 
it would return true, since we can split it up into {15, 5, 10, 15, 10} and {20, 35}, which both add up to 55.

Given the multiset {15, 5, 20, 10, 35}, it would return false, 
since we can't split it up into two subsets that add up to the same sum.

Program.cs

class Program
{
    static void Main(string[] args)
    {
        int[] a = new int[] { 15, 5, 20, 10, 35, 15, 10 };

        Console.WriteLine(Partition(a, a.Sum() / 2)); // true
    }

    private static bool Partition(int[] a, int S)
    {
        bool[,] dp = new bool[a.Length + 1, S + 1];
        dp[a.Length, S] = true;
        for (int i = a.Length - 1; i >= 0; i--)
        {
            for (int j = S; j >= 0; j--)
            {
                dp[i, j] = (j + a[i] <= S && dp[i + 1, j + a[i]]) || dp[i + 1, j];
            }
        }
        return dp[0, 0];
    }
}