“Ярмарочный подразделение” Ответ

Ярмарочный подразделение

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Solution
{
    public static void Main()
    {
        var t = Convert.ToInt32(Console.ReadLine());
        while (t-- > 0)
        {
            Solve();
        }
    }
    public static void Solve()
    {
        var N = Convert.ToInt32(Console.ReadLine());
        var list = Console.ReadLine().Trim().Split(' ').Select(x => Convert.ToInt64(x)).ToList();
        var sum = list.Sum();

        if(sum%2!=0)
        {
            System.Console.WriteLine("NO");
        }
        else
        {
            var t =DP(list,sum/2,N);
            if(t)
            {
                System.Console.WriteLine("YES");
            }
            else
            {
                System.Console.WriteLine("NO");
            }
        }
    }
    public static bool DP(List<long> ls, long w, int n)
    {
        var arr = new bool[w+1,n+1];

        for (int i = 0; i < n; i++) 
            arr[0,i]=true; 
      
        for (int i = 1; i < w; i++) 
            arr[i,0]=false; 

        for (int i = 1; i <= w; i++) 
        {
            for (int j = 1; j <= n; j++) 
            {
                arr[i,j] = arr[i,j-1];
              
                if (i >= ls[j - 1]) 
                  arr[i,j] = arr[i,j] || arr[i - ls[j - 1], j - 1];
            }
        }
        return arr[w,n];
    }
  // TLE on third test case;
    public static bool Knapsack(List<long> ls, long w, int n)
    {
        if(w==0) return true; 
        if(w<0) return false; 
        if(n<=0) return false; 
        else return Knapsack(ls,w-ls[n-1],n-1)|| Knapsack(ls,w,n-1);
    }
}