Given an array of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. 
Example 1:
Input:
N = 6
arr[] = {3, 34, 4, 12, 5, 2}
sum = 9
Output: 1 
Explanation: Here there exists a subset with
sum = 9, 4+3+2 = 9.
Example 2:
Input:
N = 6
arr[] = {3, 34, 4, 12, 5, 2}
sum = 30
Output: 0 
Explanation: There is no subset with sum 30.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isSubsetSum() which takes the array arr[], its size N and an integer sum as input parameters and returns boolean value true if there exists a subset with given sum and false otherwise.
The driver code itself prints 1, if returned value is true and prints 0 if returned value is false.
 
Expected Time Complexity: O(sum*N)
Expected Auxiliary Space: O(sum*N)
 
Constraints:
1 <= N <= 100
1<= arr[i] <= 100
1<= sum <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def isSubsetSum (self, N, arr, sum):

        # code here 

        

        

Solutions:
class Solution:

	def isSubsetSum(self, n, a, sum):
		tab = [[0] * (sum + 1) for i in range(n + 1)]
		tab[0][0] = 1
		for i in range(1, sum + 1):
			tab[0][i] = 0
		for i in range(1, n + 1):
			for j in range(sum + 1):
				if a[i - 1] <= j:
					tab[i][j] = tab[i - 1][j] + tab[i - 1][j - a[i - 1]]
				else:
					tab[i][j] = tab[i - 1][j]
		return 1 if tab[n][sum] else 0


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [False for _ in range(sum + 1)]
		for num in arr:
			if num > sum:
				continue
			for s in range(sum, 0, -1):
				if dp[s] == True and s + num <= sum:
					dp[s + num] = True
			dp[num] = True
		return dp[sum]


class Solution:

	def isSubsetSum(self, n, arr, sm):
		dp = [[False for i in range(sm + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for j in range(1, sm + 1):
			dp[0][j] = False
		for i in range(1, n + 1):
			for j in range(1, sm + 1):
				if arr[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] or dp[i - 1][j]
		return dp[n][sm]


class Solution:

	def isSubsetSum(self, n, set, sum):
		subset = [[False for i in range(sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			subset[i][0] = True
		for i in range(1, sum + 1):
			subset[0][i] = False
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				if j < set[i - 1]:
					subset[i][j] = subset[i - 1][j]
				if j >= set[i - 1]:
					subset[i][j] = subset[i - 1][j] or subset[i - 1][j - set[i - 1]]
		return subset[n][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = set()
		dp.add(0)
		for i in arr:
			temp = set()
			for j in dp:
				if j + i == sum or i == sum:
					return True
				temp.add(j + i)
				temp.add(j)
			dp = temp
		return False


class Solution:

	def isSubsetSum(self, N, arr, sum):
		n = N
		t = [[False for i in range(sum + 1)] for i in range(N + 1)]
		for i in range(1, sum + 1):
			t[0][i] = False
		for i in range(n + 1):
			t[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				if arr[i - 1] <= j:
					t[i][j] = t[i - 1][j - arr[i - 1]] or t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		return t[n][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		prev = [False] * (sum + 1)
		prev[0] = True
		if arr[0] <= sum:
			prev[arr[0]] = True
		for index in range(1, N):
			cur = [False] * (sum + 1)
			cur[0] = True
			for target in range(1, sum + 1):
				pick = False if arr[index] > target else prev[target - arr[index]]
				notPick = prev[target]
				cur[target] = pick or notPick
			prev = cur
		return prev[sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[False] * (sum + 1) for _ in range(N)]
		for i in range(N):
			dp[i][0] = True
		if arr[0] <= sum:
			dp[0][arr[0]] = True
		for index in range(1, N):
			for target in range(1, sum + 1):
				pick = False if arr[index] > target else dp[index - 1][target - arr[index]]
				notPick = dp[index - 1][target]
				dp[index][target] = pick or notPick
		return dp[N - 1][sum]


class Solution:

	def isSubsetSum(self, N, arr, target):
		dp = [[-1 for _ in range(target + 1)] for _ in range(N)]

		def f(i, target, arr):
			if target == 0:
				return True
			if i == 0:
				return arr[0] == target
			if dp[i][target] != -1:
				return dp[i][target]
			notTake = f(i - 1, target, arr)
			take = False
			if arr[i] <= target:
				take = f(i - 1, target - arr[i], arr)
			dp[i][target] = take or notTake
			return dp[i][target]
		if f(N - 1, target, arr):
			return 1
		return 0


class Solution:

	def isSubsetSum(self, N, arr, sum):

		def recursive(ind, target):
			for i in range(N + 1):
				dp[i][0] = 1
			for ind in range(1, N + 1):
				for target in range(1, target + 1):
					pick = False
					if arr[ind - 1] <= target:
						pick = dp[ind - 1][target - arr[ind - 1]]
					nonpick = dp[ind - 1][target]
					dp[ind][target] = pick or nonpick
			return dp[-1][-1]
		dp = [[0 for i in range(sum + 1)] for j in range(N + 1)]
		return recursive(0, sum)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		target = sum
		dp_prev = [False for _ in range(target + 1)]
		dp_prev[0] = True
		if arr[0] <= target:
			dp_prev[arr[0]] = True
		for r in range(1, N):
			temp = [False for _ in range(target + 1)]
			for c in range(1, target + 1):
				pick = False
				if arr[r] <= c:
					pick = dp_prev[c - arr[r]]
				no_pick = dp_prev[c]
				if pick or no_pick:
					temp[c] = True
				else:
					temp[c] = False
			dp_prev = temp
		return dp_prev[target]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[-1 for _ in range(N)] for _ in range(sum + 1)]
		return self.isSubsetSumHelper(N - 1, sum, arr, dp)

	def isSubsetSumHelper(self, pos, target, arr, dp):
		if target == 0:
			dp[0][pos] = True
			return dp[0][pos]
		if pos == 0:
			if target == arr[pos]:
				dp[0][pos] = True
				return True
			else:
				dp[0][pos] = False
				return False
		if dp[target][pos] != -1:
			return dp[target][pos]
		no_pick = self.isSubsetSumHelper(pos - 1, target, arr, dp)
		if no_pick:
			dp[target][pos] = True
			return dp[target][pos]
		pick = False
		if arr[pos] <= target:
			pick = self.isSubsetSumHelper(pos - 1, target - arr[pos], arr, dp)
		if pick:
			dp[target][pos] = True
			return dp[target][pos]
		dp[target][pos] = False
		return dp[target][pos]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		arr = [0] + arr
		v = [[0] * (sum + 1) for i in range(N + 1)]
		for i in range(0, N + 1):
			v[i][0] = 1
		for itm in range(1, N + 1):
			for w in range(1, sum + 1):
				if arr[itm] <= w:
					v[itm][w] = max(v[itm - 1][w], v[itm - 1][w - arr[itm]])
				else:
					v[itm][w] = v[itm - 1][w]
		return v[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		matrix = [[False for i in range(sum + 1)] for j in range(N + 1)]
		subArrSize = N
		for i in range(subArrSize + 1):
			for j in range(sum + 1):
				if j == 0:
					matrix[i][j] = True
				elif arr[i - 1] <= j:
					matrix[i][j] = matrix[i - 1][j - arr[i - 1]] or matrix[i - 1][j]
				else:
					matrix[i][j] = matrix[i - 1][j]
		return matrix[subArrSize][sum]


class Solution:

	def isSubsetSum(self, N, arr, tsm):
		prev = [False] * (tsm + 1)
		prev[0] = True
		if arr[0] <= tsm:
			prev[arr[0]] = True
		for i in range(1, N):
			cur = [False] * (tsm + 1)
			cur[0] = True
			for sm in range(1, tsm + 1):
				not_pick = prev[sm]
				pick = False
				if sm - arr[i] >= 0:
					pick = prev[sm - arr[i]]
				cur[sm] = not_pick or pick
			prev = cur
		return prev[tsm]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		arr = sorted(arr)
		n = len(arr)
		M = [0] * len(arr)

		def index_weight(j, sum):
			sub_w = sum - arr[j]
			for i in range(j):
				if arr[i] > sub_w:
					return i - 1
			if j == 0:
				return -1
			return i

		def calc_subsize(j, sum):
			if j == -1:
				return 0
			elif sum - arr[j] < 0:
				return 0
			else:
				return 1 + calc_subsize(index_weight(j, sum), sum - arr[j])

		def large_sum(j, sum):
			if sum - arr[j] < 0:
				return 0
			if j == -1:
				return 0
			else:
				return arr[j] + large_sum(index_weight(j, sum), sum - arr[j])
		for i in range(0, n):
			sum1 = large_sum(i, sum)
			if sum1 == sum:
				return 1
		return 0


class Solution:

	def dfs(self, i, sm, arr, dp):
		if i == -1:
			if sm == 0:
				return True
			return False
		if dp[i][sm] != -1:
			return dp[i][sm]
		not_pick = self.dfs(i - 1, sm, arr, dp)
		pick = False
		if sm - arr[i] >= 0:
			pick = self.dfs(i - 1, sm - arr[i], arr, dp)
		dp[i][sm] = not_pick or pick
		return dp[i][sm]

	def isSubsetSum(self, N, arr, sm):
		dp = [[-1 for j in range(sm + 1)] for i in range(N)]
		return self.dfs(N - 1, sm, arr, dp)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[-1 for i in range(sum + 1)] for j in range(N + 1)]

		def dfs(i, target):
			if target == 0:
				return True
			if i < 0 or target < 0:
				return False
			if dp[i][target] != -1:
				return dp[i][target]
			dp[i][target] = dfs(i - 1, target - arr[i]) or dfs(i - 1, target)
			return dp[i][target]
		return dfs(N - 1, sum)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [0 for _ in range(sum + 1)]
		dp[0] = 1
		for r in range(N):
			for c in range(sum, 0, -1):
				if c - arr[r] >= 0:
					dp[c] = dp[c] or dp[c - arr[r]]
		return dp[sum]


class Solution:

	def helper(self, arr, index, sum):
		if sum == 0:
			return True
		if index < 0:
			return False
		if self.dp[index][sum] is not None:
			return self.dp[index][sum]
		notTake = self.helper(arr, index - 1, sum)
		take = False if arr[index] > sum else self.helper(arr, index - 1, sum - arr[index])
		self.dp[index][sum] = notTake or take
		return self.dp[index][sum]

	def isSubsetSum(self, n, arr, sum):
		self.dp = [[None] * (sum + 1) for _ in range(n)]
		return self.helper(arr, n - 1, sum)


class Solution:

	def isSubsetSum(self, n, arr, sum):
		prev = [False] * (sum + 1)
		prev[0] = True
		if arr[0] <= sum:
			prev[arr[0]] = True
		for index in range(1, n):
			cur = [False] * (sum + 1)
			cur[0] = True
			for target in range(1, sum + 1):
				notTake = prev[target]
				take = False if arr[index] > target else prev[target - arr[index]]
				cur[target] = notTake or take
			prev = cur
		return prev[sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		w = sum + 1
		l = []
		for i in range(N + 1):
			d = []
			for j in range(w):
				d.append(0)
			l.append(d)
		for i in range(N + 1):
			for j in range(w):
				if i == 0:
					l[i][j] = 0
				if j == 0:
					l[i][j] = 1
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				if arr[i - 1] <= j:
					l[i][j] = l[i - 1][j - arr[i - 1]] or l[i - 1][j]
				else:
					l[i][j] = l[i - 1][j]
		return l[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, target):
		memo = {}

		def find(ind, target):
			if (ind, target) in memo:
				return memo[ind, target]
			if target == 0:
				memo[ind, target] = True
				return True
			if ind == 0:
				memo[ind, target] = arr[0] == target
				return memo[ind, target]
			take = False
			if target >= arr[ind]:
				take = find(ind - 1, target - arr[ind])
				memo[ind - 1, target - arr[ind]] = take
			not_take = find(ind - 1, target)
			memo[ind - 1, target] = not_take
			return take or not_take
		return find(N - 1, target)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		table = [[False for x in range(sum + 1)] for y in range(N + 1)]
		for i in range(N + 1):
			table[i][0] = True
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				table[i][j] = table[i - 1][j]
				if arr[i - 1] <= j:
					table[i][j] = table[i - 1][j] or table[i - 1][j - arr[i - 1]]
		return table[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[-1 for i in range(sum + 1)] for j in range(N + 1)]
		for i in range(sum + 1):
			dp[0][i] = 0
		for i in range(N + 1):
			dp[i][0] = 1
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				if arr[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - arr[i - 1]] | dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		L = [[None for i in range(sum + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			L[i][0] = True
		for j in range(1, sum + 1):
			L[0][j] = False
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				if j - arr[i - 1] < 0:
					L[i][j] = L[i - 1][j]
				else:
					L[i][j] = L[i - 1][j] or L[i - 1][j - arr[i - 1]]
		return L[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = {}

		def solve(n, sm):
			if sm == 0:
				return 1
			elif n == 0:
				return 0
			elif (n, sm) in dp:
				return dp[n, sm]
			else:
				item = arr[n - 1]
				if item <= sm:
					c1 = solve(n - 1, sm - item)
					c2 = solve(n - 1, sm)
					c = c1 or c2
				else:
					c = solve(n - 1, sm)
				dp[n, sm] = c
				return c
		return solve(N, sum)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[False for _ in range(sum + 1)] for _ in range(N + 1)]
		for i in range(N + 1):
			dp[i][0] = True
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				dp[i][j] = dp[i - 1][j] or (dp[i - 1][j - arr[i - 1]] if j - arr[i - 1] >= 0 else False)
		return dp[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = {}

		def recursion(index, currentSum):
			if currentSum < 0:
				return False
			if currentSum == 0:
				return True
			if index < 0:
				return False
			if (index, currentSum) in dp:
				return dp[index, currentSum]
			dp[index, currentSum] = recursion(index - 1, currentSum) or recursion(index - 1, currentSum - arr[index])
			return dp[index, currentSum]
		return recursion(N - 1, sum)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [False] * (sum + 1)
		dp[0] = True
		for element in arr:
			for j in range(sum, element - 1, -1):
				if dp[j - element]:
					dp[j] = True
		return dp[-1]


class Solution:

	def isSubsetSum(self, n, arr, sum):
		dp = [[False for j in range(sum + 1)] for i in range(n)]
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)
		for i in range(n):
			dp[i][0] = True
		if arr[0] <= sum:
			dp[0][arr[0]] = True
		for i in range(1, n):
			for j in range(sum + 1):
				npick = dp[i - 1][j]
				pick = False
				if arr[i] <= j:
					pick = dp[i - 1][j - arr[i]]
				dp[i][j] = pick or npick
		return dp[n - 1][sum]

	def solve(self, i, j, arr, dp):
		if i == 0:
			return arr[0] == j
		if j == 0:
			dp[i][j] = True
			return dp[i][j]
		if dp[i][j] != -1:
			return dp[i][j]
		npick = self.solve(i - 1, j, arr, dp)
		pick = False
		if arr[i] <= j:
			pick = self.solve(i - 1, j - arr[i], arr, dp)
		dp[i][j] = pick or npick
		return dp[i][j]


def isSubsetSum(set, n, sum, dp):
	if sum == 0:
		return True
	if n == 0:
		return False
	if dp[n - 1][sum] != -1:
		return dp[n - 1][sum]
	if set[n - 1] > sum:
		ans = isSubsetSum(set, n - 1, sum, dp)
	else:
		ans = isSubsetSum(set, n - 1, sum, dp) or isSubsetSum(set, n - 1, sum - set[n - 1], dp)
	dp[n - 1][sum] = ans
	return ans

class Solution:

	def isSubsetSum(self, n, set, sum):
		dp = [[-1] * (sum + 1) for i in range(n + 1)]
		if isSubsetSum(set, n, sum, dp) == True:
			return 1
		else:
			return 0


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [False for _ in range(10 ** 5 + 1)]
		dp[0] = True
		dp[arr[0]] = True
		for i in range(1, N):
			temp = [False for _ in range(10 ** 5 + 1)]
			for target in range(1, sum + 1):
				take = False
				if target >= arr[i]:
					take = dp[target - arr[i]]
				noTake = dp[target]
				temp[target] = take or noTake
			dp = temp
		return dp[sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[-1] * 100000 for _ in range(100)]

		def helper(ind, target):
			if target == 0:
				return True
			if ind == N:
				return False
			if dp[ind][target] != -1:
				return dp[ind][target]
			not_take = helper(ind + 1, target)
			take = helper(ind + 1, target - arr[ind])
			dp[ind][target] = take or not_take
			return dp[ind][target]
		return helper(0, sum)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[None for _ in range(10 ** 5 + 1)] for _ in range(100 + 1)]
		return self.rec(0, N, arr, sum, dp)

	def rec(self, i, N, arr, s, dp):
		if s == 0:
			return True
		if i >= N:
			return False
		if dp[i][s] != None:
			return dp[i][s]
		take = False
		if s >= arr[i]:
			take = self.rec(i + 1, N, arr, s - arr[i], dp)
		noTake = self.rec(i + 1, N, arr, s, dp)
		dp[i][s] = take or noTake
		return take or noTake


class Solution:

	def isSubsetSum(self, n, arr, target):
		dp = [[0] * (target + 1) for i in range(n)]
		for i in range(n):
			dp[i][0] = True
		if arr[0] <= target:
			dp[0][arr[0]] = True
		for i in range(1, n):
			for tg in range(1, target + 1):
				nt = dp[i - 1][tg]
				t = False
				if target >= arr[i]:
					t = dp[i - 1][tg - arr[i]]
				dp[i][tg] = nt or t
		return dp[n - 1][target]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		s = sum
		t = [[-1 for i in range(s + 1)] for i in range(N + 1)]

		def F(arr, 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 arr[N - 1] > s:
				t[N][s] = F(arr, N - 1, s, t)
			else:
				t[N][s] = F(arr, N - 1, s - arr[N - 1], t) or F(arr, N - 1, s, t)
			return t[N][s]
		return F(arr, N, s, t)


from collections import defaultdict

class Solution:

	def isSubsetSum(self, n, set, sum):
		subset = [[False for i in range(sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			subset[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				if j < set[i - 1]:
					subset[i][j] = subset[i - 1][j]
				if j >= set[i - 1]:
					subset[i][j] = subset[i - 1][j] or subset[i - 1][j - set[i - 1]]
		return subset[n][sum]


from collections import defaultdict

class Solution:

	def isSubsetSum(self, N, arr, s):
		dp = {}

		def sum(i, arr, s, dp):
			if s == 0:
				return True
			if s < 0:
				return False
			if i < 0:
				return False
			if dp.get((i, s), -1) != -1:
				return dp[i, s]
			t = sum(i - 1, arr, s, dp)
			n = False
			if arr[i] <= s:
				n = sum(i - 1, arr, s - arr[i], dp)
			dp[i, s] = t or n
			return dp[i, s]
		return sum(N - 1, arr, s, dp)


class Solution:

	def isSubsetSum(self, n, arr, sum):
		arr.sort()
		dp = [[0 for i in range(sum + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(sum + 1):
				if i == 0 and j == 0:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] = 0
				elif j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j]
					if j >= arr[i - 1]:
						if dp[i - 1][j - arr[i - 1]] == 1:
							dp[i][j] = 1
		if dp[n][sum] == 1:
			return 1
		return 0


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[None for _ in range(sum + 1)] for _ in range(N + 1)]
		for i in range(0, sum + 1):
			dp[0][i] = 0
		for i in range(0, N + 1):
			dp[i][0] = 1
		for i in range(1, N + 1):
			for j in range(1, sum + 1):
				take = False
				not_take = dp[i - 1][j]
				if j >= arr[i - 1]:
					take = dp[i - 1][j - arr[i - 1]]
				dp[i][j] = take or not_take
		return dp[N][sum]


class Solution:

	def isSubsetSum(self, n, arr, sum):
		dp = [[0 for _ in range(sum + 1)] for __ in range(n + 1)]
		for i in range(n):
			dp[i][0] = 1
		if arr[0] <= sum:
			dp[0][arr[0]] = 1
		for idx in range(1, n):
			for target in range(1, sum + 1):
				nottake = dp[idx - 1][target]
				take = 0
				if target >= arr[idx]:
					take = dp[idx - 1][target - arr[idx]]
				dp[idx][target] = 1
				if take == 0 and nottake == 0:
					dp[idx][target] = 0
		return dp[n - 1][sum]


class Solution:

	def isSubsetSum(self, N, arr, key):
		dp = [[0] * (key + 1) for i in range(N + 1)]
		for i in range(N + 1):
			dp[i][0] = 1
		for i in range(1, N + 1):
			for j in range(1, key + 1):
				if arr[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] | dp[i - 1][j - arr[i - 1]]
		return True if dp[N][key] else False


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = {}

		def find_sum(target, idx):
			if (target, idx) in dp:
				return dp[target, idx]
			if target == 0:
				dp[target, idx] = True
				return True
			if idx >= N or target < 0:
				dp[target, idx] = False
				return False
			take = False
			if target - arr[idx] >= 0:
				take = find_sum(target - arr[idx], idx + 1)
			skip = find_sum(target, idx + 1)
			res = take or skip
			dp[target, idx] = res
			return res
		out = find_sum(sum, 0)
		if out:
			return 1
		else:
			return 0


class Solution:

	def func(self, idx, target, dp):
		if target == 0:
			return True
		if idx < 0:
			return False
		if (idx, target) in dp:
			return dp[idx, target]
		if target >= arr[idx]:
			dp[idx, target] = self.func(idx - 1, target - arr[idx], dp) or self.func(idx - 1, target, dp)
		else:
			dp[idx, target] = self.func(idx - 1, target, dp)
		return dp[idx, target]

	def isSubsetSum(self, N, arr, sum):
		dp = {}
		x = self.func(N - 1, sum, dp)
		return x


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = []
		p = []
		for i in range(len(arr) + 1):
			for j in range(sum + 1):
				p.append(0)
			dp.append(p)
			p = []
		for i in range(len(arr) + 1):
			for j in range(sum + 1):
				if j == 0:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] = 0
				elif dp[i - 1][j] == 1:
					dp[i][j] = 1
				else:
					val = arr[i - 1]
					if j >= val and dp[i - 1][j - val] == 1:
						dp[i][j] = 1
		return dp[-1][-1]


class Solution:

	def isSubsetSum(self, n, arr, k):
		bucket = {}

		def solve(idx, tillNow):
			if idx == n:
				if tillNow == k:
					return True
				else:
					return False
			if (idx, tillNow) in bucket:
				return bucket[idx, tillNow]
			if solve(idx + 1, tillNow + arr[idx]):
				bucket[idx, tillNow] = True
				return bucket[idx, tillNow]
			if solve(idx + 1, tillNow):
				bucket[idx, tillNow] = True
				return bucket[idx, tillNow]
			bucket[idx, tillNow] = False
			return bucket[idx, tillNow]
		return solve(0, 0)


class Solution:

	def isSubsetSum(self, N, arr, sum):
		return self.isSubsetSumTabOpt(N, arr, sum)

	def isSubsetSumRecur(self, N, arr, sum, dp):
		if sum == 0:
			return True
		if N == 0:
			return arr[N] == sum
		if dp[N][sum] != -1:
			return dp[N][sum]
		not_selected = self.isSubsetSumRecur(N - 1, arr, sum, dp)
		selected = False
		if sum >= arr[N]:
			selected = self.isSubsetSumRecur(N - 1, arr, sum - arr[N], dp)
		dp[N][sum] = 1 if not_selected or selected else 0
		return dp[N][sum]

	def isSubsetSumTab(self, N, arr, sum):
		dp = [[True if i == 0 else False for i in range(sum + 1)] for _ in range(N)]
		if arr[0] <= sum:
			dp[0][arr[0]] = True
		for i in range(1, N):
			for target in range(1, sum + 1):
				not_taken = dp[i - 1][target]
				taken = False
				if target >= arr[i]:
					taken = dp[i - 1][target - arr[i]]
				dp[i][target] = taken or not_taken
		return dp[N - 1][sum]

	def isSubsetSumTabOpt(self, N, arr, sum):
		dp = [True if i == 0 else False for i in range(sum + 1)]
		if arr[0] <= sum:
			dp[arr[0]] = True
		for i in range(1, N):
			curr = [True if i == 0 else False for i in range(sum + 1)]
			for target in range(1, sum + 1):
				not_taken = dp[target]
				taken = False
				if target >= arr[i]:
					taken = dp[target - arr[i]]
				curr[target] = taken or not_taken
			dp = curr
		return dp[sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = [[-1 for _ in range(sum + 1)] for _ in range(N)]
		self.isSubsetSumRecur(N - 1, arr, sum, dp)
		return dp[N - 1][sum]

	def isSubsetSumRecur(self, N, arr, sum, dp):
		if sum == 0:
			return True
		if N == 0:
			return arr[N] == sum
		if dp[N][sum] != -1:
			return dp[N][sum]
		not_selected = self.isSubsetSumRecur(N - 1, arr, sum, dp)
		selected = False
		if sum >= arr[N]:
			selected = self.isSubsetSumRecur(N - 1, arr, sum - arr[N], dp)
		dp[N][sum] = 1 if not_selected or selected else 0
		return dp[N][sum]


class Solution:

	def isSubsetSum(self, N, arr, Sum):
		dp = [[-1 for i in range(Sum + 1)] for i in range(N + 1)]
		return self.subset(N - 1, arr, Sum, dp)

	def subset(self, n, arr, target, dp):
		if target == 0:
			return True
		if n == 0:
			return arr[0] == target
		if dp[n][target] != -1:
			return dp[n][target]
		nottake = self.subset(n - 1, arr, target, dp)
		take = False
		if target >= arr[n]:
			take = self.subset(n - 1, arr, target - arr[n], dp)
		dp[n][target] = take or nottake
		return dp[n][target]


class Solution:

	def isSubsetSum(self, N, arr, sum):

		def subset(ind, target):
			if target == 0:
				return True
			if ind == 0:
				return True if arr[ind] == target else False
			if dp[ind][target] != -1:
				return dp[ind][target]
			notTake = subset(ind - 1, target)
			Take = False
			if arr[ind] <= target:
				Take = subset(ind - 1, target - arr[ind])
			dp[ind][target] = notTake or Take
			return dp[ind][target]
		dp = [[-1 for i in range(sum + 1)] for i in range(N)]
		subset(N - 1, sum)
		return dp[N - 1][sum]


class Solution:

	def isSubsetSum(self, N, arr, sum):
		dp = {}

		def solve(n, cap):
			if cap == 0:
				return 1
			elif n == 0:
				return 0
			elif (n, cap) in dp:
				return dp[n, cap]
			elif arr[n - 1] <= cap:
				ans = solve(n - 1, cap - arr[n - 1]) or solve(n - 1, cap)
			else:
				ans = solve(n - 1, cap)
			dp[n, cap] = ans
			return ans
		return solve(N, sum)