Subset Sum Problem in O ( sum ) space | Returns true if there exists a subset with given sum in arr [ ] ; The value of subset [ i % 2 ] [ j ] will be true if there exists a subset of sum j in arr [ 0 , 1 , ... . , i - 1 ] ; A subset with sum 0 is always possible ; If there exists no element no sum is possible ; Driver code
def isSubsetSum ( arr , n , sum ) : NEW_LINE INDENT subset = [ [ False for j in range ( sum + 1 ) ] for i in range ( 3 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( sum + 1 ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT subset [ i % 2 ] [ j ] = True NEW_LINE DEDENT elif ( i == 0 ) : NEW_LINE INDENT subset [ i % 2 ] [ j ] = False NEW_LINE DEDENT elif ( arr [ i - 1 ] <= j ) : NEW_LINE INDENT subset [ i % 2 ] [ j ] = subset [ ( i + 1 ) % 2 ] [ j - arr [ i - 1 ] ] or subset [ ( i + 1 ) % 2 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT subset [ i % 2 ] [ j ] = subset [ ( i + 1 ) % 2 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT return subset [ n % 2 ] [ sum ] NEW_LINE DEDENT arr = [ 6 , 2 , 5 ] NEW_LINE sum = 7 NEW_LINE n = len ( arr ) NEW_LINE if ( isSubsetSum ( arr , n , sum ) == True ) : NEW_LINE INDENT print ( " There ▁ exists ▁ a ▁ subset ▁ with ▁ given ▁ sum " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ subset ▁ exists ▁ with ▁ given ▁ sum " ) NEW_LINE DEDENT