Given an integer array coins[ ] of size N representing different denominations of currency and an integer sum, find the number of ways you can make sum by using different combinations from coins[ ].  
Note: Assume that you have an infinite supply of each type of coin.  
Example 1:
Input:
sum = 4 , 
N = 3
coins[] = {1,2,3}
Output: 4
Explanation: Four Possible ways are:
{1,1,1,1},{1,1,2},{2,2},{1,3}.
Example 2:
Input:
Sum = 10 , 
N = 4
coins[] ={2,5,3,6}
Output: 5
Explanation: Five Possible ways are:
{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} 
and {5,5}.
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which accepts an array coins[ ] its size N and sum as input parameters and returns the number of ways to make change for given sum of money. 
Expected Time Complexity: O(sum*N)
Expected Auxiliary Space: O(sum)
Constraints:
1 <= sum, N <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def count(self, coins, N, Sum):

        # code here 



Solutions:
class Solution:

	def count(self, coins, N, Sum):
		table = [0 for k in range(sum + 1)]
		table[0] = 1
		for i in range(0, N):
			for j in range(coins[i], sum + 1):
				table[j] += table[j - coins[i]]
		return table[Sum]


class Solution:

	def count(self, coins, n, sum):
		dp = [[-1 for a in range(sum + 1)] for b in range(n + 1)]
		for q in range(sum + 1):
			dp[0][q] = 0
		for w in range(n + 1):
			dp[w][0] = 1
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				if coins[i - 1] <= j:
					dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][sum]


class Solution:

	def count(self, coins, N, Sum):
		dp = [[1 for i in range(Sum + 1)] for j in range(N + 1)]
		for i in range(1, Sum + 1):
			dp[0][i] = 0
		for i in range(1, N + 1):
			for j in range(Sum + 1):
				if coins[i - 1] <= j:
					dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[i][j]


class Solution:

	def count(self, coins, N, Sum):
		table = [[0 for _ in range(Sum + 1)] for _ in range(N)]
		for k in range(N):
			table[k][0] = 1
		for i in range(N):
			for j in range(Sum + 1):
				if i == 0 and j == 0:
					table[i][j] = 1
				if coins[i] > j:
					table[i][j] = table[i - 1][j]
				else:
					table[i][j] = table[i - 1][j] + table[i][j - coins[i]]
		return table[-1][-1]


class Solution:

	def count(self, coins, N, Sum):
		l = [0 for i in range(Sum + 1)]
		l[0] = 1
		for coin in coins:
			for i in range(coin, Sum + 1):
				l[i] += l[i - coin]
		return l[-1]


class Solution:

	def count(self, coins, N, Sum):
		dp = [0] * (Sum + 1)
		dp[0] = 1
		for j in range(len(coins)):
			for i in range(coins[j], Sum + 1):
				dp[i] += dp[i - coins[j]]
		return dp[sum]


class Solution:

	def count(self, coins, n, sum):
		dp = [[-1 for i in range(sum + 1)] for j in range(n + 1)]

		def memo(i, target):
			if target == 0:
				return 1
			if i < 0:
				return 0
			if dp[i][target] != -1:
				return dp[i][target]
			if coins[i] <= target:
				dp[i][target] = memo(i, target - coins[i]) + memo(i - 1, target)
			else:
				dp[i][target] = memo(i - 1, target)
			return dp[i][target]
		return memo(n - 1, sum)


class Solution:

	def count(self, coins, N, Sum):
		dp = [0] * (Sum + 1)
		dp[0] = 1
		for coin in coins:
			for sumvalue in range(coin, Sum + 1):
				dp[sumvalue] += dp[sumvalue - coin]
		return dp[Sum]


class Solution:

	def count(self, coins, N, sum):
		table = [[0 for x in range(N)] for x in range(sum + 1)]
		for i in range(N):
			table[0][i] = 1
		for i in range(1, sum + 1):
			for j in range(N):
				x = table[i - coins[j]][j] if i - coins[j] >= 0 else 0
				y = table[i][j - 1] if j >= 1 else 0
				table[i][j] = x + y
		return table[sum][N - 1]


class Solution:

	def count(self, coins, ns, n):
		dp = [[0] * (n + 1) for i in range(len(coins) + 1)]
		for i in range(len(coins) + 1):
			dp[i][0] = 1
		for i in range(1, len(coins) + 1):
			for j in range(1, n + 1):
				if coins[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[len(coins)][n]


class Solution:

	def count(self, coins, n, sum_):
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		dp = [[-1 for j in range(sum_ + 1)] for i in range(n)]
		return self.solve(n - 1, sum_, coins, dp)

	def solve(self, n, ts, coins, dp):
		if n == 0:
			if ts % coins[n] == 0:
				dp[n][ts] = 1
				return 1
			else:
				dp[n][ts] = 0
				return 0
		if dp[n][ts] != -1:
			return dp[n][ts]
		pick = 0
		npick = self.solve(n - 1, ts, coins, dp)
		if coins[n] <= ts:
			pick = self.solve(n, ts - coins[n], coins, dp)
		dp[n][ts] = pick + npick
		return dp[n][ts]


class Solution:

	def count(self, coins, n, sum_):
		dp = [[0 for j in range(sum_ + 1)] for i in range(n)]
		for j in range(sum_ + 1):
			if j % coins[0] == 0:
				dp[0][j] = 1
		for i in range(1, n):
			for j in range(sum_ + 1):
				npick = dp[i - 1][j]
				pick = 0
				if coins[i] <= j:
					pick = dp[i][j - coins[i]]
				dp[i][j] = pick + npick
		return dp[n - 1][sum_]


class Solution:

	def count(self, coins, N, amount):
		dp = [0] * (amount + 1)
		dp[0] = 1
		for i in range(N):
			for j in range(coins[i], amount + 1):
				dp[j] += dp[j - coins[i]]
		return dp[-1]


from functools import lru_cache

class Solution:

	def count(self, coins, N, Sum):
		coins.sort()

		@lru_cache(None)
		def dp(cur, idx):
			if cur == 0:
				return 1
			if idx == N or coins[idx] > cur:
				return 0
			return dp(cur - coins[idx], idx) + dp(cur, idx + 1)
		return dp(Sum, 0)


from functools import lru_cache

class Solution:

	def count(self, coins, N, Sum):
		coins.sort()

		@lru_cache(None)
		def dp(cur, idx):
			if cur == 0:
				return 1
			count = 0
			for i in range(idx, N):
				if coins[i] > cur:
					break
				count += dp(cur - coins[i], i)
			return count
		return dp(Sum, 0)


class Solution:

	def count(self, coins, N, Sum):
		coins.sort()
		dp = [[0] * (Sum + 1) for _ in range(N + 1)]
		for r in range(N + 1):
			dp[r][0] = 1
		for r in range(1, N + 1):
			for c in range(Sum + 1):
				if coins[r - 1] <= c:
					dp[r][c] = dp[r - 1][c] + dp[r][c - coins[r - 1]]
				else:
					dp[r][c] = dp[r - 1][c]
		return dp[-1][-1]


class Solution:

	def answer(self, coins, i, sum, dp):
		if sum == 0:
			return 1
		if i == -1:
			return 0
		if dp[i][sum] != -1:
			return dp[i][sum]
		pick = 0
		if sum >= coins[i]:
			pick = self.answer(coins, i, sum - coins[i], dp)
		notpick = self.answer(coins, i - 1, sum, dp)
		dp[i][sum] = pick + notpick
		return dp[i][sum]

	def count(self, coins, N, Sum):
		dp = [[-1 for i in range(Sum + 1)] for j in range(N)]
		return self.answer(coins, N - 1, Sum, dp)


class Solution:

	def count(self, a, N, t):
		dp = [0 for i in range(t + 1)]
		temp = [0 for i in range(t + 1)]
		for i in range(t + 1):
			if i % a[0] == 0:
				dp[i] = 1
		for i in range(1, len(a)):
			for j in range(t + 1):
				x = dp[j]
				y = 0
				if a[i] <= j:
					y = temp[j - a[i]]
				temp[j] = x + y
			dp = temp
		return dp[t]


class Solution:

	def count(self, coins, N, Sum):
		return self.bottom_up_count(coins, N, Sum)

	def bottom_up_count(self, coins, N, Sum):
		dp = [[0] * N for _ in range(Sum + 1)]
		for i in range(N):
			dp[0][i] = 1
		for i in range(1, Sum + 1):
			for j in range(N):
				x = dp[i - coins[j]][j] if i - coins[j] >= 0 else 0
				y = dp[i][j - 1] if j - 1 >= 0 else 0
				dp[i][j] = x + y
		return dp[Sum][N - 1]


class Solution:

	def count(self, coins, n, sum):
		dp = [0] * (sum + 1)
		dp[0] = 1
		for j in range(n):
			for i in range(coins[j], sum + 1):
				dp[i] += dp[i - coins[j]]
		return dp[sum]


import numpy as np

class Solution:

	def rec_sol(self, coins, N, Sum):
		if Sum == 0:
			return 1
		if Sum < 0:
			return 0
		if N == 0:
			return 0
		return self.rec_sol(coins, N, Sum - coins[N - 1]) + self.rec_sol(coins, N - 1, Sum)

	def memo_sol(self, coins, N, Sum, dp):
		if Sum == 0:
			return 1
		if Sum < 0:
			return 0
		if N == 0:
			return 0
		if dp[N][Sum] != -1:
			return dp[N][Sum]
		dp[N][Sum] = self.memo_sol(coins, N, Sum - coins[N - 1], dp) + self.memo_sol(coins, N - 1, Sum, dp)
		return dp[N][Sum]

	def dp_sol(self, coins, N, Sum):
		dp = np.array([[0] * (Sum + 1)] * (N + 1))
		for i in range(1, N + 1):
			for j in range(Sum + 1):
				if j == 0:
					dp[i][j] = 1
				elif j - coins[i - 1] >= 0:
					dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[N][Sum]

	def dp_sol_opt(self, coins, N, Sum):
		dp = np.array([0] * (Sum + 1))
		for i in range(1, N + 1):
			for j in range(Sum + 1):
				if j == 0:
					dp[j] = 1
				elif j - coins[i - 1] >= 0:
					dp[j] = dp[j - coins[i - 1]] + dp[j]
		return dp[Sum]

	def count(self, coins, N, Sum):
		return self.dp_sol_opt(coins, N, Sum)


import numpy as np

class Solution:

	def rec_sol(self, coins, N, Sum):
		if Sum == 0:
			return 1
		if Sum < 0:
			return 0
		if N == 0:
			return 0
		return self.rec_sol(coins, N, Sum - coins[N - 1]) + self.rec_sol(coins, N - 1, Sum)

	def memo_sol(self, coins, N, Sum, dp):
		if Sum == 0:
			return 1
		if Sum < 0:
			return 0
		if N == 0:
			return 0
		if dp[N][Sum] != -1:
			return dp[N][Sum]
		dp[N][Sum] = self.memo_sol(coins, N, Sum - coins[N - 1], dp) + self.memo_sol(coins, N - 1, Sum, dp)
		return dp[N][Sum]

	def count(self, coins, N, Sum):
		dp = np.array([[-1] * (Sum + 1)] * (N + 1))
		return self.memo_sol(coins, N, Sum, dp)


class Solution:

	def count(self, coins, N, Sum):
		dp = [[0] * (Sum + 1) for row in range(N)]
		for j in range(Sum + 1):
			dp[0][j] = j % coins[0] == 0
		for i in range(1, N):
			for j in range(0, Sum + 1):
				notPick = 0 + dp[i - 1][j]
				pick = 0
				if j >= coins[i]:
					pick = dp[i][j - coins[i]]
				dp[i][j] = pick + notPick
		return dp[N - 1][Sum]


class Solution:

	def solution(self, ind, arr, T, dp):
		if ind == 0:
			return T % arr[ind] == 0
		if dp[ind][T] != -1:
			return dp[ind][T]
		notPick = 0 + self.solution(ind - 1, arr, T, dp)
		pick = 0
		if T >= arr[ind]:
			pick = self.solution(ind, arr, T - arr[ind], dp)
		dp[ind][T] = pick + notPick
		return dp[ind][T]

	def count(self, coins, N, Sum):
		dp = [[-1] * (Sum + 1) for rows in range(N + 1)]
		return self.solution(N - 1, coins, Sum, dp)


class Solution:

	def solution(self, ind, T, coins, dp):
		if ind == 0:
			return T % coins[ind] == 0
		if dp[ind][T] != -1:
			return dp[ind][T]
		notTake = 0 + self.solution(ind - 1, T, coins, dp)
		take = 0
		if coins[ind] <= T:
			take = self.solution(ind, T - coins[ind], coins, dp)
		dp[ind][T] = take + notTake
		return dp[ind][T]

	def count(self, coins, N, Sum):
		dp = [[-1] * (Sum + 1) for rows in range(N + 1)]
		return self.solution(N - 1, Sum, coins, dp)


class Solution:

	def count(self, coins, N, Sum):
		T = [[0 for i in range(Sum + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			for j in range(Sum + 1):
				if i == 0:
					T[i][j] = 0
				if j == 0 and i != 0:
					T[i][j] = 1
				elif coins[i - 1] <= j:
					T[i][j] = T[i][j - coins[i - 1]] + T[i - 1][j]
				else:
					T[i][j] = T[i - 1][j]
		return T[N][Sum]


class Solution:

	def count(self, coins, N, Sum):
		d = {}

		def f(n, s=Sum):
			k = (n, s)
			if n == 0:
				if s % coins[n] == 0:
					return 1
				else:
					return 0
			if k in d:
				return d[k]
			else:
				nt = f(n - 1, s)
				t = 0
				if s >= coins[n]:
					t = f(n, s - coins[n])
			d[k] = t + nt
			return d[k]
		return f(N - 1)


class Solution:

	def count(self, coins, N, Sum):
		t = [[-1 for i in range(Sum + 1)] for i in range(N + 1)]

		def Count(coins, N, Sum, t):
			W = Sum
			if W == 0:
				return 1
			if N == 0:
				return 0
			if t[N][W] != -1:
				return t[N][W]
			if coins[N - 1] <= W:
				t[N][W] = Count(coins, N, W - coins[N - 1], t) + Count(coins, N - 1, W, t)
			elif coins[N - 1] > W:
				t[N][W] = Count(coins, N - 1, W, t)
			return t[N][W]
		return Count(coins, N, Sum, t)


class Solution:

	def count(self, coins, N, Sum):
		t = [[-1 for i in range(Sum + 1)] for j in range(N + 1)]

		def f(coins, n, s, t):
			if n == 0 and s != 0:
				return 0
			if s == 0:
				return 1
			if t[n][s] != -1:
				return t[n][s]
			if coins[n - 1] > s:
				t[n][s] = f(coins, n - 1, s, t)
			else:
				t[n][s] = f(coins, n, s - coins[n - 1], t) + f(coins, n - 1, s, t)
			return t[n][s]
		return f(coins, N, Sum, t)


class Solution:

	def solve(coins, N, Sum, dp):
		if N == 0:
			return 0
		if Sum == 0:
			return 1
		if dp[N][Sum] != -1:
			return dp[N][Sum]
		if coins[N - 1] > Sum:
			dp[N][Sum] = Solution.solve(coins, N - 1, Sum, dp)
			return dp[N][Sum]
		dp[N][Sum] = Solution.solve(coins, N - 1, Sum, dp) + Solution.solve(coins, N, Sum - coins[N - 1], dp)
		return dp[N][Sum]

	def count(self, coins, N, Sum):
		dp = [[-1 for _ in range(Sum + 1)] for _ in range(N + 1)]
		return Solution.solve(coins, N, Sum, dp)


class Solution:

	def solve(self, idx, coins, N, target):
		if target == 0:
			return 1
		if target < 0 or idx >= N:
			return 0
		incl = 0
		if coins[idx] <= target:
			incl = self.solve(idx, coins, N, target - coins[idx])
		excl = self.solve(idx + 1, coins, N, target)
		return incl + excl

	def solve_memo(self, idx, coins, N, target, F):
		if target == 0:
			return 1
		if target < 0 or idx >= N:
			return 0
		if F[idx][target] != -1:
			return F[idx][target]
		incl = 0
		if coins[idx] <= target:
			incl = self.solve_memo(idx, coins, N, target - coins[idx], F)
		excl = self.solve_memo(idx + 1, coins, N, target, F)
		F[idx][target] = incl + excl
		return F[idx][target]

	def solve_tab(self, coins, N, Sum):
		F = [[0 for _ in range(Sum + 1)] for _ in range(N + 1)]
		for i in range(N + 1):
			F[i][0] = 1
		for idx in range(N - 1, -1, -1):
			for target in range(1, Sum + 1):
				incl = 0
				if target - coins[idx] >= 0:
					incl = F[idx][target - coins[idx]]
				excl = F[idx + 1][target]
				F[idx][target] = incl + excl
		return F[0][Sum]

	def solve_opt(self, coins, N, Sum):
		curr = [0 for _ in range(Sum + 1)]
		nxt = [0 for _ in range(Sum + 1)]
		for idx in range(N - 1, -1, -1):
			curr[0] = 1
			for target in range(1, Sum + 1):
				incl = 0
				if target - coins[idx] >= 0:
					incl = curr[target - coins[idx]]
				excl = nxt[target]
				curr[target] = incl + excl
			nxt = curr[:]
		return nxt[Sum]

	def count(self, coins, N, Sum):
		return self.solve_opt(coins, N, Sum)


class Solution:

	def count(self, coins, N, Sum):
		dp = [[0] * (Sum + 1) for _ in range(N + 1)]
		for i in range(N + 1):
			for j in range(Sum + 1):
				if j == 0:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] == 0
				else:
					val = coins[i - 1]
					if val <= j:
						c1 = dp[i][j - val]
						c2 = dp[i - 1][j]
						dp[i][j] = c1 + c2
					else:
						dp[i][j] = dp[i - 1][j]
		return dp[N][Sum]


class Solution:

	def count(self, coins, N, Sum):
		count_ = [0 for i in range(Sum + 1)]
		count_[0] = 1
		for den in coins:
			for j in range(den, Sum + 1):
				count_[j] += count_[j - den]
		return count_[Sum]


class Solution:

	def count(self, coins, N, Sum):
		h = {0: 1}
		if Sum == 0:
			return 1
		if not coins:
			return 0
		for coin in coins:
			for num in range(1, Sum + 1):
				if num - coin in h:
					ways = h[num - coin]
				else:
					ways = 0
				h[num] = h[num] + ways if num in h else ways
		return h[Sum]