Modify array by merging elements with addition such that it consists of only Primes . | DP array to store the ans for max 20 elements ; To check whether the number is prime or not ; Function to check whether the array can be modify so that there are only primes ; If curr is prime and all elements are visited , return true ; If all elements are not visited , set curr = 0 , to search for new prime sum ; If all elements are visited ; If the current sum is not prime return false ; If this state is already calculated , return the answer directly ; Try all state of mask ; If ith index is not set ; Add the current element and set ith index and recur ; If subset can be formed then return true ; After every possibility of mask , if the subset is not formed , return false by memoizing . ; Driver code
dp = [ 0 ] * ( 1 << 20 ) NEW_LINE def isprime ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def solve ( arr , curr , mask , n ) : NEW_LINE INDENT if ( isprime ( curr ) ) : NEW_LINE INDENT if ( mask == ( 1 << n ) - 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT curr = 0 NEW_LINE DEDENT if ( mask == ( 1 << n ) - 1 ) : NEW_LINE INDENT if ( isprime ( curr ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if ( dp [ mask ] != False ) : NEW_LINE INDENT return dp [ mask ] NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( ( mask & 1 << i ) == False ) : NEW_LINE INDENT if ( solve ( arr , curr + arr [ i ] , mask 1 << i , n ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return ( dp [ mask ] == False ) NEW_LINE DEDENT arr = [ 3 , 6 , 7 , 13 ] NEW_LINE n = len ( arr ) NEW_LINE if ( solve ( arr , 0 , 0 , n ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT