Given three integers n, k, target, and an array of coins of size n. Find if it is possible to make a change of target cents by using an infinite supply of each coin but the total number of coins used must be exactly equal to k.
Example 1:
Input:
n = 5, k = 3, target = 11
coins = {1, 10, 5, 8, 6}
Output: 
1
Explanation: 
2 coins of 5 and 1 coins of 1 can be used 
to make change of 11 i.e. 11 => 5+5+1.
Example 2:
Input:
n = 3, k = 5, target = 25
coins = {7, 2, 4}
Output:
1
Explanation:
3 coins 7, 2 coins of 2 can be used to
make change of 25 i.e. 25 => 7+7+7+2+2.
Your Task:
This is a function problem. You only need to complete the function makeChanges() that 3 integers n, k, target, and an array coins as parameters and return True or False.
Expected Time Complexity: O(n*k*target)
Expected Space Complexity: O(k*target)
Constraints:
1 <= n, k, coins[i] <= 100
1 <= target <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: from typing import List





class Solution:

    def makeChanges(self, N : int, K : int, target : int, coins : List[int]) -> bool:

        # code here

        



Solutions:
from typing import List

class Solution:

	def __init__(self):
		self.table = None

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		if self.table is None:
			self.table = list(([-1] * (target + 1) for k in range(K + 1)))
		if K == 0:
			return target == 0
		if self.table[K][target] != -1:
			return self.table[K][target]
		for c in coins:
			if target - c < 0:
				continue
			if self.makeChanges(N, K - 1, target - c, coins):
				self.table[K][target] = True
				return True
		self.table[K][target] = False
		return False


from typing import List

class Solution:

	def makeChanges(self, n, k, target, coins):
		table = [[False] * (k + 1) for _ in range(target + 1)]
		table[0][0] = True
		for c in coins:
			for i in range(c, target + 1):
				for j in range(1, k + 1):
					table[i][j] |= table[i - c][j - 1]
		return table[target][k]


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = [[False] * (K + 1) for i in range(target + 1)]
		dp[0][0] = True
		for i in range(1, target + 1):
			for j in range(K + 1):
				for coin in coins:
					if coin <= i and j > 0 and dp[i - coin][j - 1]:
						dp[i][j] = True
						break
		return dp[target][K]


from typing import List

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:
		dp = [[False] * (target + 1) for _ in range(k + 1)]
		dp[0][0] = True
		for i in range(1, k + 1):
			for j in range(1, target + 1):
				for l in coins:
					if j < l:
						continue
					dp[i][j] |= dp[i - 1][j - l]
		return dp[k][target]


from typing import List

class Solution:

	def solve(self, coins, ind, summ, ite, dp):
		if summ == 0 and ite == 0:
			return True
		if dp[ite][summ] != -1:
			return dp[ite][summ]
		elif summ < 0 or ite <= 0 or ind <= 0:
			return 0
		if summ >= coins[ind - 1]:
			dp[ite][summ] = self.solve(coins, ind, summ - coins[ind - 1], ite - 1, dp) or self.solve(coins, ind - 1, summ, ite, dp)
		else:
			dp[ite][summ] = self.solve(coins, ind - 1, summ, ite, dp)
		return dp[ite][summ]

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = [[-1 for i in range(target + 1)] for k in range(K + 1)]
		res = self.solve(coins, N, target, K, dp)
		return res


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = [[0] * (target + 1) for _ in range(K)]
		for coin in coins:
			if coin <= target:
				dp[0][coin] = 1
		for coin in coins:
			for k in range(1, K):
				for t in range(coin, target + 1):
					if dp[k - 1][t - coin]:
						dp[k][t] = 1
			if dp[K - 1][target]:
				return True
		return dp[K - 1][target]


from typing import List
from functools import lru_cache

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:

		@lru_cache(None)
		def recur(amt, k):
			if not k:
				return amt == 0
			res = False
			for c in coins:
				if c <= amt:
					res = res or recur(amt - c, k - 1)
			return res
		return recur(target, k)


from typing import List
import random

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = [[False] * (target + 1) for i in range(K + 1)]
		dp[0][0] = True
		for cc in range(1, K + 1):
			for val in range(0, target + 1):
				for i in coins:
					if i <= val:
						dp[cc][val] = dp[cc - 1][val - i] | dp[cc][val]
		return dp[K][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = [[False for j in range(1001)] for i in range(K + 1)]
		dp[0][0] = True
		for i in range(1, K + 1):
			for j in range(target + 1):
				if dp[i - 1][j]:
					for k in range(N):
						dp[i][j + coins[k]] = True
		return dp[K][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:
		ans = [[False for i in range(target + 1)] for i in range(k + 1)]
		ans[0][0] = True
		for i in range(len(coins)):
			for key in range(1, k + 1):
				for value in range(1, target + 1):
					if coins[i] <= value and ans[key][value] == False:
						ans[key][value] = ans[key - 1][value - coins[i]]
		return ans[k][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		(prev, cur) = (set(coins), set())
		for times in range(1, K):
			cur.clear()
			for v in prev:
				for c in coins:
					if v + c > target:
						break
					cur.add(v + c)
			(prev, cur) = (cur, prev)
		return target in prev


from typing import List
from functools import lru_cache

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:
		dp = []
		for i in range(k + 1):
			arr = []
			for j in range(target + 1):
				arr.append(False)
			dp.append(arr)
		dp[0][0] = True
		coins.sort()
		for i in range(1, k + 1):
			for j in range(target + 1):
				for c in coins:
					if c > j:
						break
					if dp[i][j] == False:
						dp[i][j] = dp[i - 1][j - c]
		return dp[k][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:
		dp = [[0 for _ in range(target + 1)] for _ in range(k + 1)]
		coin_set = set(coins)
		dp[0] = [1 if i in coin_set else 0 for i in range(target + 1)]
		for i in range(1, k + 1):
			for j in range(1, target + 1):
				for c in coins:
					if j >= c:
						prev = dp[i - 1][j - c]
						dp[i][j] |= prev
		return dp[k - 1][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		(prev, curr) = (set(coins), set())
		for i in range(1, k):
			curr.clear()
			for v in prev:
				for c in coins:
					if c + v > target:
						break
					curr.add(c + v)
			(prev, curr) = (curr, prev)
		return target in prev


from typing import List

class Solution:

	def makeChanges(self, n: int, k: int, target: int, coins: List[int]) -> bool:
		dp = [[False for i in range(target + 1)] for j in range(k + 1)]
		dp[0][0] = True
		for i in range(n):
			for j in range(1, k + 1):
				for l in range(1, target + 1):
					if coins[i] <= l and dp[j][l] == False:
						dp[j][l] = dp[j - 1][l - coins[i]]
		return dp[k][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, k: int, target: int, coins: List[int]) -> bool:
		dp = [[0] * (k + 1) for _ in range(target + 1)]
		dp[0][0] = 1
		coins.sort()
		for t in range(target):
			for n in range(k):
				for coin in coins:
					if t + 1 - coin < 0:
						break
					dp[t + 1][n + 1] += dp[t + 1 - coin][n]
		return dp[target][k]


from typing import List

class Solution:

	def makeChanges(self, N, K, target, coins):
		moves = [0] * (target + 1)
		for i in range(N):
			if coins[i] <= target:
				moves[coins[i]] = 1
		for i in range(1, K):
			freshmoves = [0] * (target + 1)
			for j in range(target + 1):
				if moves[j] == 1:
					for k in range(N):
						if j + coins[k] <= target:
							freshmoves[j + coins[k]] = 1
			moves = freshmoves
		return moves[target] == 1


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		(Prev, Curr) = (set(coins), set())
		for i in range(1, K):
			Curr.clear()
			for v in Prev:
				for j in coins:
					if v + j > target:
						break
					Curr.add(v + j)
			(Prev, Curr) = (Curr, Prev)
		return target in Prev


from typing import List

class Solution:

	def makeChanges(self, n: int, k: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		dp = [[True] * (k + 1) for _ in range(target + 1)]
		return self.func(n - 1, k, target, coins, dp)

	def func(self, cur: int, k: int, x: int, arr: List[int], dp: List[List[bool]]) -> bool:
		if k == 0 and x == 0:
			return True
		if cur < 0:
			return False
		if not dp[x][k]:
			return dp[x][k]
		for i in range(k + 1):
			if arr[cur] * i > x:
				break
			if self.func(cur - 1, k - i, x - arr[cur] * i, arr, dp):
				return True
		dp[x][k] = False
		return False


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = [set() for _ in range(target)]
		for coin in coins:
			if target > coin - 1:
				dp[coin - 1].add(1)
		for i in range(1, target):
			for coin in coins:
				if i - coin >= 0:
					for num in list(dp[i - coin]):
						dp[i].add(num + 1)
		return K in dp[-1]


from typing import List

class Solution:

	def makeChanges(self, n: int, k: int, target: int, coins: List[int]) -> bool:
		t = [[False] * (target + 1) for _ in range(K + 1)]
		t[0][0] = True
		for c in coins:
			for j in range(1, K + 1):
				for l in range(c, target + 1):
					if t[j - 1][l - c]:
						t[j][l] = True
		return t[K][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		k = K
		dp = [[-1 for _ in range(target + 1)] for _ in range(K + 1)]
		dp[0][0] = 1
		try:
			for i in range(1, k + 1):
				for j in range(1, target + 1):
					ans = False
					for l in coins:
						if j - l >= 0 and i > 0:
							if dp[i - 1][j - l] == 1:
								ans = True
							if ans:
								break
					if ans == True:
						dp[i][j] = 1
					else:
						dp[i][j] = 0
		except:
			print('j i', dp, i, j)
		return dp[k][target]


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:

		def solve(N, K, target, coins, arr):
			if target == 0 and K == 0:
				return True
			if arr[K][target] != -1:
				return arr[K][target]
			ans = False
			for i in range(N):
				if target >= coins[i] and K - 1 >= 0:
					new = solve(N, K - 1, target - coins[i], coins, arr)
					ans = ans or new
			arr[K][target] = ans
			return ans
		arr = [[-1] * (target + 1) for j in range(K + 1)]
		return solve(N, K, target, coins, arr)


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		ways = [0 for i in range(target + 1)]
		for i in range(N):
			if coins[i] <= target:
				ways[coins[i]] = 1
		for i in range(1, K):
			newWays = [0 for i in range(target + 1)]
			for j in range(target + 1):
				if ways[j] == 1:
					for k in range(N):
						if j + coins[k] <= target:
							newWays[j + coins[k]] = 1
			ways = newWays
		return ways[target] == 1


from typing import List

class Solution:

	def solve(self, N, K, target, coins, dp):
		if K == 0 and target == 0:
			return True
		if dp[K][target] != None:
			return dp[K][target]
		ans = False
		for i in range(N):
			if target >= coins[i] and K - 1 >= 0:
				ans |= self.solve(N, K - 1, target - coins[i], coins, dp)
		dp[K][target] = ans
		return ans

	def makeChanges(self, N, K, target, coins):
		dp = [[None for _ in range(target + 1)] for _ in range(K + 1)]
		return self.solve(N, K, target, coins, dp)


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		dp = dict()

		def rec(target, ind, k):
			if ind == len(coins):
				if k == 0 and target == 0:
					return True
				return False
			if target == 0:
				if k == 0:
					return True
				return False
			if k == 0:
				if target == 0:
					return True
				return False
			if (target, ind, k) not in dp:
				ans = False
				if coins[ind] <= target:
					ans = ans or rec(target - coins[ind], ind, k - 1) or rec(target - coins[ind], ind + 1, k - 1) or rec(target, ind + 1, k)
				dp[target, ind, k] = ans
			return dp[target, ind, k]
		return rec(target, 0, K)


from typing import List

class Solution:

	def helper(self, ind, n, k, target, coins, dp):
		if k == 0:
			if target == 0:
				return 1
			else:
				return 0
		if target == 0:
			if k == 0:
				return 1
			else:
				return 0
		elif ind == n and (k != 0 or target != 0):
			return 0
		if (ind, k, target) in dp:
			return dp[ind, k, target]
		take = 0
		if target - coins[ind] >= 0:
			if self.helper(ind, n, k - 1, target - coins[ind], coins, dp) == True:
				return True
		nottake = self.helper(ind + 1, n, k, target, coins, dp)
		dp[ind, k, target] = take or nottake
		return dp[ind, k, target]

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		dp = {}
		return self.helper(0, N, K, target, coins, dp)


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		try:
			coins.sort()
			dp = [[False for i in range(target + 1)] for j in range(K + 1)]
			dp[0][0] = True
			for i in range(1, N + 1):
				for j in range(1, K + 1):
					for k in range(coins[i - 1], target + 1):
						dp[j][k] = dp[j][k] or dp[j - 1][k - coins[i - 1]]
			return dp[K][target]
		except Exception as e:
			print(e, i, j, k, k - coins[i - 1], dp)


from typing import List

class Solution:

	def __init__(self) -> None:
		self.memo = set()

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		if K == 0 or target < 0:
			if target == 0:
				return True
			return False
		elif '{K}.{target}'.format(K=K, target=target) in self.memo:
			return False
		for coin in coins:
			if self.makeChanges(N, K - 1, target - coin, coins):
				return True
		self.memo.add('{K}.{target}'.format(K=K, target=target))
		return False


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		(prev, cur) = (set(coins), set())
		for i in range(1, K):
			cur = set()
			for p in prev:
				for q in coins:
					if p + q > target:
						break
					cur.add(p + q)
			(prev, cur) = (cur, prev)
		return target in prev


from typing import List

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:
		coins.sort()
		(p, c) = (set(coins), set())
		for i in range(1, K):
			c.clear()
			for j in p:
				for k in coins:
					if j + k > target:
						break
					c.add(j + k)
			(p, c) = (c, p)
		return target in p


from typing import List
from functools import lru_cache

class Solution:

	def makeChanges(self, N: int, K: int, target: int, coins: List[int]) -> bool:

		@lru_cache(None)
		def dfs(t, k):
			if t == 0 and k == 0:
				return 1
			if t == 0 or k == 0:
				return 0
			ans = 0
			for c in coins:
				if t - c >= 0:
					ans += dfs(t - c, k - 1)
			return ans
		return dfs(target, K)


from typing import List

class Solution:

	def makeChanges(self, n: int, k: int, tar: int, a: List[int]) -> bool:

		def f(i, t, c):
			if c == k:
				return t == tar
			if t > tar or i == n:
				return False
			if dp[t][c] != -1:
				return dp[t][c]
			np = f(i + 1, t, c)
			p = False
			if t + a[i] <= tar:
				p = f(i, t + a[i], c + 1)
			dp[t][c] = np or p
			return np or p
		dp = [[-1 for i in range(k + 1)] for j in range(tar + 1)]
		return f(0, 0, 0)


from typing import List

class Solution:

	def makeChanges(self, N, K, target, coins):
		memo = [[-1] * (target + 1) for _ in range(K + 1)]

		def dp(i, j, k):
			if i == 0:
				return j == 0 and k == 0
			if memo[k][j] != -1:
				return memo[k][j]
			x = dp(i - 1, j, k)
			y = 0
			if j >= coins[i - 1] and k >= 1:
				y = dp(i, j - coins[i - 1], k - 1)
			memo[k][j] = x + y
			return memo[k][j]
		return dp(N, target, K)