Count unique paths with given sum in an N | Java 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
import java . io . * ; import java . util . * ; class GFG { static int mod = ( int ) 1e9 + 7 ; static int findTotalPath ( int X , int n , ArrayList < Integer > dp ) { if ( X == 0 ) { return 1 ; } int ans = 0 ; if ( dp . get ( X ) != - 1 ) { return dp . get ( X ) ; } for ( int i = 1 ; i <= Math . min ( X , n ) ; ++ i ) { ans += findTotalPath ( X - i , n , dp ) % mod ; ans %= mod ; } dp . set ( X , ans ) ; return ans ; } public static void main ( String [ ] args ) { int n = 3 , X = 2 ; ArrayList < Integer > dp = new ArrayList < Integer > ( Collections . nCopies ( X + 1 , - 1 ) ) ; System . out . print ( findTotalPath ( X , n , dp ) ) ; } }