Number of ways to add up to a sum S with N numbers

Given an array of unique number and sum. There are many combinations and subsets of an array that come up with given sum. 

Example : 

Input : A[] = {1,2,4,5,9}

           sum = 15

Output: 2

Combinations are {1,5,9} and {1,2,4,5}

Input: A[] = {2,3,5,6,8,10}

          Sum = 10 

Output: 3

Combinations are {2,3,5}, {2,8} and {10}

A = [2,3,5,8,10]

total = 10

#initialize all elements to zero first

arr = [[0 for x in range(len(A)+1)] for y in range(len(A)+1)]

arr[0][0] = 1 

index_dict = {0:0} #Stores element and its index in array

for ind, y in enumerate(A):

    index_dict[y] = ind+1

for i in range(1,len(A)+1):

    arr[i] = [x for x in arr[i-1]] #Duplicate upper row

    for j in range(i,len(A)+1):

        diff = A[j-1]-A[i-1]

        if diff in index_dict: #If difference found in present list

            indx = index_dict[diff]

            arr[i][j] = arr[i-1][j] + arr[i-1][indx] #Update with its possible combination

 print arr[-1][-1]      

NA	Array Elements					0
0	2	3	5	8	10	Subtract from
1	0	0	0	0	0	0
1	1	0	0	0	0	2
1	1	1	1	0	0	3
1	1	1	2	1	1	5
1	1	1	2	2	2	8
1	1	1	2	2	3	10

#perfectsumproblem #geeksforgeeks #ways #combinations #subset #subsequence #array #dynamicprogramming