using System;

using System.Collections.Generic;       

public class Program

{

      /*

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.

    */

    // optimize it  using memoaization 

    public static bool CanBePartitioned(int [] array){

        int sum=0;

        foreach(int num in array){

            sum+=num;

        }

        Dictionary<string,bool>memo = new Dictionary<string,bool>();

        return can_be_partitioned(sum,array,0,ref memo);

    }

    public static bool can_be_partitioned(int sum,int[]array,int idx, ref Dictionary<string,bool> memo){

        if(sum==0)

            return true;

        if(sum<0||idx==array.Length)

            return false;

        int num=array[idx];

        string key=num.ToString()+","+sum.ToString();

        if(memo.ContainsKey(key))

            return memo[key];

        bool result= can_be_partitioned(sum-num,array,idx+1,ref memo)||can_be_partitioned(sum,array,idx+1,ref memo);

        memo.Add(key,result);

        return memo[key];

    }

    public static void Main()

    {

        Console.WriteLine(CanBePartitioned(new int[]{15, 5, 20, 10, 35, 15, 10}));

    }

}