Count of subsets with sum equal to X | Python3 implementation of the approach ; To store the states of DP ; Function to return the required count ; Base case ; If the state has been solved before return the value of the state ; Setting the state as solved ; Recurrence relation ; Driver code
import numpy as np NEW_LINE maxN = 20 NEW_LINE maxSum = 50 NEW_LINE minSum = 50 NEW_LINE base = 50 NEW_LINE dp = np . zeros ( ( maxN , maxSum + minSum ) ) ; NEW_LINE v = np . zeros ( ( maxN , maxSum + minSum ) ) ; NEW_LINE def findCnt ( arr , i , required_sum , n ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT if ( required_sum == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT DEDENT if ( v [ i ] [ required_sum + base ] ) : NEW_LINE INDENT return dp [ i ] [ required_sum + base ] ; NEW_LINE DEDENT v [ i ] [ required_sum + base ] = 1 ; NEW_LINE dp [ i ] [ required_sum + base ] = findCnt ( arr , i + 1 , required_sum , n ) + findCnt ( arr , i + 1 , required_sum - arr [ i ] , n ) ; NEW_LINE return dp [ i ] [ required_sum + base ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 3 , 3 , 3 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE x = 6 ; NEW_LINE print ( findCnt ( arr , 0 , x , n ) ) ; NEW_LINE DEDENT