# Q)Find largest possible prime number that can be generated by adding all the elements of any subset of the given array. 
# Return -1 if it is impposible.
# Implement the method largestPrime() below

# 	------------------------------
# 	Constraints:
# 	Length of array < 16
# 	Each element in array is zero or a positive integer < 10000
# 	------------------------------

# 	Example
# 		Input:
# 		[3, 3, 2, 2]

# 		Output:
# 		7


# 		Input:
# 		[0, 2, 4, 1, 2, 4, 4]

# 		Output:
# 		17


# 		Input:
# 		[6]

# 		Output:
# 		-1





# Implement this method to return the expected output

import itertools

def largestPrime(a):
    allPrimes = []
    for i in range(1,len(a)+1):
        allCombs = list(itertools.combinations(a,i))
        for j in allCombs:
            req_num = sum(j)
            if req_num == 2 | req_num == 3:
                allPrimes.append(req_num)
            isPrime = []
            if (req_num > 1) & (req_num != 2) & (req_num != 3): 
               for i in range(2, req_num//2):
                   if (req_num % i) == 0:
                       isPrime.append(0)
                       break 
                   else:
                       isPrime.append(1)
            else:
                isPrime.append(0)
            if 1 in isPrime and 0 not in isPrime:
                allPrimes.append(req_num)
    if allPrimes:
        return max(allPrimes)
    else:
        return -1
    
# No need to change below this
# No need to change below this
# No need to change below this
# No need to change below this
# No need to change below this
#################################################################################################################
#################################################################################################################
#################################################################################################################
#################################################################################################################
#################################################################################################################
#################################################################################################################
#################################################################################################################
#################################################################################################################
#################################################################################################################
# No need to change below this
import traceback
def testLargestPrime():
	data = [
		[3, 3, 2, 2],
		[0, 2, 4, 1, 2, 4, 4],
		[6],
		[87, 47, 33],
		[772, 312, 421, 706, 258, 583],
		[854, 964, 59, 747, 753, 511, 40, 340, 703],
		[2, 9],
		[7, 6, 5, 2, 2, 5, 0, 0],
		[36, 81, 37, 89, 36, 77, 89, 33, 36, 45],
		[0,3,49]

	]
	
	output = [7, 17, -1, 167, 1697, 4931, 11, 23, 523, 3]

	accepted = 0
	for i in range(len(data)):
		try:			
			print ("Test case: " + str(i))
			print ("Input:")
			print (str(data[i]))
			print ("Expected output:")
			print (output[i])
			print ("Actual Output:")			
			ans = largestPrime(data[i])
			print (ans)
			if(ans == output[i]):
				accepted +=1
		except:
			print(traceback.format_exc())

		print ("\n\n")

	print ("Verdict:")
	if(accepted == len(output)):
		print ("------All test passed-------")
	else:
		print ("-----Test Failed: " + str(accepted) + " tests passed out of " + str(len(output)) + "-----")	


testLargestPrime()