using System;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("PartitionEqualSubsetSum");

        var nums = new int[]{ 2, 2, 4, 1, 1 };

        var target = nums.Sum() / 2;

        memo = new bool?[nums.Length+1, target+1];

        Console.WriteLine(CheckPartitionEqualSumDPMemo(nums, 0, nums.Length, target));

    }

    public static bool CheckPartitionEqualSum(int[] nums, int i, int n, int target)

    {

        if(target == 0)

            return true;

        if(i >= n)

            return false;

        return CheckPartitionEqualSum(nums, i+1, n, target) || CheckPartitionEqualSum(nums, i+1, n, target-nums[i]);

    }

    private static bool?[,] memo;

    public static bool CheckPartitionEqualSumDPMemo(int[] nums, int i, int n, int target)

    {

        if(target == 0)

            return true;

        if(target < 0)

            return false;

        if(i >= n)

            return false;

        if(memo[i, target].HasValue)

            return memo[i, target].Value;

        else

        {

            var result = CheckPartitionEqualSum(nums, i+1, n, target) || CheckPartitionEqualSum(nums, i+1, n, target-nums[i]);

            memo[i, target] = result;

            return result;

        }

    }

}