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_1 : A[] = {1,2,4,5,9}
sum = 15

Output_1: 2
Combinations are {1,5,9} and {1,2,4,5}.

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

Output_2: 3
Combinations are {2,3,5}, {2,8} and {10}.

#!/bin/python
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]

Explanation :

	Array Elements
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

Array Elements
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