Dynamic Programming | Taking the matrix as globally ; Check if possible subset with given sum is possible or not ; If the sum is zero it means we got our expected sum ; If the value is not - 1 it means it already call the function with the same value . it will save our from the repetition . ; if the value of a [ n - 1 ] is greater than the sum . we call for the next value ; Here we do two calls because we don ' t ▁ know ▁ which ▁ value ▁ is ▁ ▁ full - fill ▁ our ▁ criteria ▁ ▁ that ' s why we doing two calls ; Driver Code
tab = [ [ - 1 for i in range ( 2000 ) ] for j in range ( 2000 ) ] NEW_LINE def subsetSum ( a , n , sum ) : NEW_LINE INDENT if ( sum == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( n <= 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( tab [ n - 1 ] [ sum ] != - 1 ) : NEW_LINE INDENT return tab [ n - 1 ] [ sum ] NEW_LINE DEDENT if ( a [ n - 1 ] > sum ) : NEW_LINE INDENT tab [ n - 1 ] [ sum ] = subsetSum ( a , n - 1 , sum ) NEW_LINE return tab [ n - 1 ] [ sum ] NEW_LINE DEDENT else : NEW_LINE INDENT tab [ n - 1 ] [ sum ] = subsetSum ( a , n - 1 , sum ) NEW_LINE return tab [ n - 1 ] [ sum ] or subsetSum ( a , n - 1 , sum - a [ n - 1 ] ) NEW_LINE DEDENT DEDENT n = 5 NEW_LINE a = [ 1 , 5 , 3 , 7 , 4 ] NEW_LINE sum = 12 NEW_LINE if ( subsetSum ( a , n , sum ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT