Count unique paths with given sum in an N | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define ll  long long NEW_LINE using namespace std ; const int mod = ( int ) 1e9 + 7 ; ll findTotalPath ( int X , int n , vector < int > & dp ) { if ( X == 0 ) { return 1 ; } ll ans = 0 ; if ( dp [ X ] != -1 ) { return dp [ X ] ; } for ( int i = 1 ; i <= min ( X , n ) ; ++ i ) { ans += findTotalPath ( X - i , n , dp ) % mod ; ans %= mod ; } return dp [ X ] = ans ; } int main ( ) { int n = 3 , X = 2 ; vector < int > dp ( X + 1 , -1 ) ; cout << findTotalPath ( X , n , dp ) ; }