The Indian Job

                            Solution in C :

In C++ :





#include <stdio.h>
#include <string.h>

#define NMAX 101
#define VMAX 10001

int A[NMAX];
char ok[VMAX];
int N, G, i, j, sum;

int main() {
	int T;
	scanf("%d", &T);

	while (T--) {
		scanf("%d %d", &N, &G);
		for (sum = 0, i = 1; i <= N; i++) {
			scanf("%d", &(A[i]));
			sum += A[i];
		}

		memset(ok, 0, sizeof(ok));
		ok[0] = 1;
		for (i = 1; i <= N; i++)
			for (j = VMAX - 1 - A[i]; j >= 0; j--)
				if (ok[j]) ok[j + A[i]] = 1;

		for (i = 0; i < VMAX; i++)
			if (ok[i] && i <= G && (sum - i) <= G) {
				printf("YES\n");
				break;
			}

		if (i == VMAX)
			printf("NO\n");
	}

	return 0;
}








In Java :





import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Solution {

    void solve() throws IOException {
        int t=nextInt();
        for(int testCase=0;testCase<t;testCase++){
            int n=nextInt();
            int g=nextInt();
            int[] a=new int[n];
            int sum=0;
            for(int i=0;i<n;i++){
                a[i]=nextInt();
                sum+=a[i];
            }
            if(g>=sum){
                out.println("YES");
                continue;
            }
            if(sum>2*g){
                out.println("NO");
                continue;
            }
            boolean[][] dp=new boolean[n+1][g+1];
            dp[0][0]=true;
            for(int i=0;i<n;i++){
                for(int j=0;j<g;j++)
                    if(dp[i][j]){
                        dp[i+1][j]=true;
                        if(j+a[i]<=g)dp[i+1][j+a[i]]=true;
                    }
            }
            int max=0;
            for(int i=g;i>=0;i--)
                if(dp[n][i]){
                    max=i;
                    break;
                }
            if(sum-max<=g){
                out.println("YES");
            }
            else
                out.println("NO");
        }
    }

    public static void main(String[] args) throws IOException {
        new Solution().run();
    }

    void run() throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
//		reader = new BufferedReader(new FileReader("input.txt"));
        tokenizer = null;
        out = new PrintWriter(new OutputStreamWriter(System.out));
//		out = new PrintWriter(new FileWriter("output.txt"));
        solve();
        reader.close();
        out.flush();

    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}








In C :





#include <stdio.h>
#include <string.h>

int dp[101][5001];

int main()
{
	int T, N;
	int G;
	int A[100];

	scanf("%d", &T);
	for(int i=0; i<T; i++)
	{
		int sum = 0;
		int s;
		memset(A, 0, sizeof(A));
		memset(dp, 0, sizeof(dp));
		scanf("%d%d", &N, &G);
		
		for(int j=1; j<=N; j++)
		{
			scanf("%d", &A[j]);
			sum += A[j];			
		}
		dp[0][0] = 1;
		
		/*for(int k1=1; k1<=N; k1++)
		   for(int k2=k1; k2>=1; k2--)
			for(s=1; s<=(sum>>1); s++)
			{
				if(s >= A[k1] && dp[k2-1][s-A[k1]])
					dp[k2][s] = 1;
			}
		
		for(int k=2; k<=N; k++)
			for(s=1; s<=sum/2; s++)
				if(dp[k-1][s])
					dp[k][s] = 1; */
		for(int k=1; k<=N; k++)
			for(s=0; s<=sum/2; s++)
			{
				if(s >= A[k])
					dp[k][s] = dp[k-1][s-A[k]] || dp[k-1][s];
				else
					dp[k][s] = dp[k-1][s];
			}

		for(s=(sum>>1); s>=1 && !dp[N][s]; s--) ;
		if(sum/2 > s)
			s = sum - s;
		if(s > G)
			printf("NO\n");
		else
			printf("YES\n");
	}
}








In Python3 :





import itertools

def nzerolast(l):
  for i in range(len(l)-1, -1, -1):
    if l[i] > 0:
      return i
  return 0

T = int(input())
for _ in range(T):
  N, G = map(int, input().split())
  L = list(itertools.repeat(0, G + 1))
  nl = list(map(int, input().split()))
  L[0] = 1
  for num in nl:
    for g in range(G, num - 1, -1):
      L[g] += L[g - num]
  can = nzerolast(L)
  print("YES" if sum(nl) - can <= G else "NO")