Count unique paths with given sum in an N | Python3 program for the above approach ; Function for counting total no of paths possible with the sum is equal to X ; If the path of the sum from the root to current node is stored in sum ; If already computed ; Count different no of paths using all possible ways ; Return total no of paths ; Driver Code ; Stores the number of ways to obtains sums 0 to X ; Function call
mod = int ( 1e9 + 7 ) NEW_LINE def findTotalPath ( X , n , dp ) : NEW_LINE INDENT if ( X == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT ans = 0 NEW_LINE if ( dp [ X ] != - 1 ) : NEW_LINE INDENT return dp [ X ] NEW_LINE DEDENT for i in range ( 1 , min ( X , n ) + 1 ) : NEW_LINE INDENT ans = ans + findTotalPath ( X - i , n , dp ) % mod ; NEW_LINE ans %= mod ; NEW_LINE DEDENT dp [ X ] = ans NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 3 NEW_LINE X = 2 NEW_LINE dp = [ - 1 ] * ( X + 1 ) NEW_LINE print ( findTotalPath ( X , n , dp ) ) NEW_LINE DEDENT