Dhiraj loves Chocolates.He loves chocolates so much that he can eat up to $1000$ chocolates a day. But his mom is fed up by this habit of him and decides to take things in her hand.
Its diwali Season and Dhiraj has got a lot of boxes of chocolates and Dhiraj's mom is afraid that dhiraj might eat all boxes of chocolates.
So she told Dhiraj that he can eat only exactly $k$ number of chocolates and dhiraj has to finish all the chocolates in box selected by him and then move on to next box of chocolate.Now Dhiraj is confused that whether he will be able to eat $k$ number of chocolates or not. Since dhiraj is weak at maths,he asks for your help to tell him whether he can eat $k$ number of chocolates or not. 
So given number of chocolates  are $k$ which dhiraj has to eat and the boxes of chocolates each containing some number of chocolates, tell whether dhiraj will be able to eat $k$ number of chocolates or not.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- $k$, representing the number of chocolates dhiraj has to eat.
- the third line contains $N$ representing the no. of boxes of chocolates.
- fourth line contains list of $a[]$ size $N$ specifying the number of chocolates in each Box.

-----Output:-----
- For each testcase, output in a single line answer $0$ or $1$.
- $0$ if dhiraj cant eat $k$ chocolates from given combination and $1$ if he can eat $k$ chocolates from given combination.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 10^7$
- $1 \leq  N \leq 800$
- $1 \leq a[i] \leq 10^3$

-----Sample Input:-----
2
20
5
8 7 2 10 5
11
4
6 8 2 10

-----Sample Output:-----
1
0

Difficulty: interview

Starter code:

Solutions:
def isSubsetSum(arr, n, sum): 
    subset = [ [False for j in range(sum + 1)] for i in range(3) ]    
    for i in range(n + 1): 
        for j in range(sum + 1): 
            if (j == 0):subset[i % 2][j] = True
            elif (i == 0):subset[i % 2][j] = False
            elif (arr[i - 1] <= j):subset[i % 2][j] = subset[(i + 1) % 2][j - arr[i - 1]] or subset[(i + 1)% 2][j] 
            else:subset[i % 2][j] = subset[(i + 1) % 2][j]                   
    return subset[n % 2][sum]  
for _ in range(int(input())):
    k,n,a = int(input()),int(input()),list(map(int,input().split()))
    if sum(a) < k or k < min(a):print(0);continue
    print(1) if isSubsetSum(a, n, k) else print(0)

def isSubsetSum(arr, n, sum): 
     
    # The value of subset[i%2][j] will be true  
    # if there exists a subset of sum j in  
    # arr[0, 1, ...., i-1] 
    subset = [ [False for j in range(sum + 1)] for i in range(3) ] 
   
    for i in range(n + 1): 
        for j in range(sum + 1): 
            # A subset with sum 0 is always possible  
            if (j == 0): 
                subset[i % 2][j] = True
   
            # If there exists no element no sum  
            # is possible  
            elif (i == 0): 
                subset[i % 2][j] = False
            elif (arr[i - 1] <= j): 
                subset[i % 2][j] = subset[(i + 1) % 2][j - arr[i - 1]] or subset[(i + 1)  
                                                                               % 2][j] 
            else: 
                subset[i % 2][j] = subset[(i + 1) % 2][j] 
                  
    return subset[n % 2][sum]  
		
# Driver program to test above function 
for _ in range(int(input())):
    k = int(input())
    n = int(input())
    a = list(map(int,input().split()))
    if sum(a) < k or k < min(a):
        print(0)
        continue
    if (isSubsetSum(a, n, k) == True): 
	    print(1) 
    else: 
	    print(0)

def isSubsetSum(set, n, sum):
    # The value of subset[i][j] will be
    # true if there is a 
    # subset of set[0..j-1] with sum equal to i 
    subset = ([[False for i in range(sum + 1)]
               for i in range(n + 1)])

    # If sum is 0, then answer is true  
    for i in range(n + 1):
        subset[i][0] = True

    # If sum is not 0 and set is empty,  
    # then answer is false  
    for i in range(1, sum + 1):
        subset[0][i] = False

    # Fill the subset table in botton up manner 
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if j < set[i - 1]:
                subset[i][j] = subset[i - 1][j]
            if j >= set[i - 1]:
                subset[i][j] = (subset[i - 1][j] or
                                subset[i - 1][j - set[i - 1]])

                # uncomment this code to print table
    # for i in range(n + 1): 
    # for j in range(sum + 1): 
    # print(subset[i][j], end =" ") 
    # print() 
    return subset[n][sum]

for _ in range(int(input())):
    K = int(input())
    N = int(input())
    array = list(map(int, input().split()))
    if K > sum(array):
        print(0)
    elif isSubsetSum(array, N , K):
        print(1)
    else:
        print(0)