Count of Ways to obtain given Sum from the given Array elements | Python3 program to implement the above approach ; Function to call dfs to calculate the number of ways ; Iterate till the length of array ; Initialize the memorization table ; Function to perform the DFS to calculate the number of ways ; Base case : Reached the end of array ; If current sum is obtained ; Otherwise ; If previously calculated subproblem occurred ; Check if the required sum can be obtained by adding current element or by subtracting the current index element ; Store the count of ways ; Driver Code
import sys NEW_LINE def findWays ( nums , S ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( len ( nums ) ) : NEW_LINE INDENT sum += nums [ i ] NEW_LINE DEDENT memo = [ [ - sys . maxsize - 1 for i in range ( 2 * sum + 1 ) ] for j in range ( len ( nums ) + 1 ) ] NEW_LINE return dfs ( memo , nums , S , 0 , 0 , sum ) NEW_LINE DEDENT def dfs ( memo , nums , S , curr_sum , index , sum ) : NEW_LINE INDENT if ( index == len ( nums ) ) : NEW_LINE INDENT if ( S == curr_sum ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if ( memo [ index ] [ curr_sum + sum ] != - sys . maxsize - 1 ) : NEW_LINE INDENT return memo [ index ] [ curr_sum + sum ] NEW_LINE DEDENT ans = ( dfs ( memo , nums , index + 1 , curr_sum + nums [ index ] , S , sum ) + dfs ( memo , nums , index + 1 , curr_sum - nums [ index ] , S , sum ) ) NEW_LINE memo [ index ] [ curr_sum + sum ] = ans NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = 3 NEW_LINE arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE answer = findWays ( arr , S ) NEW_LINE print ( answer ) NEW_LINE DEDENT