josephs-coin-trouble

Joseph studies at SKIT.He is a fresher he has been given a task and he wants help from you for performing the task.The task is an interesting one.

The tasks is:-

He is provided with a value N, he has to make change for N cents, and he have infinite supply of each of S = { S1, S2, S3, S4} 
valued coins, how many ways can he make the change? The order of coins doesn't matter.
Maximum types of coins available are only 4. 

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.

Now his job is to find out no of ways he can make the change as for above example the result will be 4.

INPUT

First line denotes N.
Second line denotes S which is no of types of coins in string format.

OUTPUT

An integer which shows the no of ways he can make the change

CONSTRAINTS

MAXIMUM VALUE OF N,S1,S2,S3,S4 CAN BE 9000000.

SAMPLE INPUT
10
2 4 9

SAMPLE OUTPUT
3

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
# your code goes here
def count(x,m,n):
	if(n==0):
		return 1
	if(n<0):
		return 0
	if(m<=0 and n>=1):
		return 0
	return count(x,m-1,n)+count(x,m,n-x[m-1])	
	
n=int(eval(input()))
x=list(map(int,input().split()))
print(count(x,len(x),n))


n = int(input())
a = list(map(int, input().split()))
s = [[0 for i in range(len(a))] for i in range(n+1)]
for i in range(len(a)):
	s[0][i] = 1
x = 0
y = 0
for i in range(1, n+1):
	for j in range(len(a)):
		if i - a[j] >= 0:
			x = s[i-a[j]][j]
		else:
			x = 0
		if j >= 1:
			y = s[i][j-1]
		else:
			y = 0
		s[i][j] = x+y

print(s[n][len(a)-1])