Given an array arr and target sum k, check whether there exists a subsequence such that the sum of all elements in the subsequence equals the given target sum(k).
Example:
Input:  arr = [10,1,2,7,6,1,5], k = 8.
Output:  Yes
Explanation:  Subsequences like [2, 6], [1, 7] sum upto 8
Input:  arr = [2,3,5,7,9], k = 100. 
Output:  No
Explanation:  No subsequence can sum upto 100
Your Task:
You don't need to read or print anything. Your task is to complete the boolean function checkSubsequenceSum() which takes N, arr and K as input parameter and returns true/false based on the whether any subsequence with sum K could be found.
Expected Time Complexity: O(N * K).
Expected Auxiliary Space: O(N * K).
Constraints:
1 <= arr.length <= 2000.
1 <= arr[i] <= 1000.
1 <= target <= 2000.

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def checkSubsequenceSum(self, N, arr, K):

        # Code here

Solutions:
class Solution:

	def checkSubsequenceSum(self, N, arr, K):
		dp = [0] * (K + 1)
		dp[0] = 1
		for a in arr:
			for i in range(K, -1, -1):
				if i - a >= 0:
					dp[i] += dp[i - a]
		return dp[K] >= 1


class Solution:

	def checkSubsequenceSum(self, N, arr, K):
		dp = [[True if i == 0 else False for i in range(K + 1)] for j in range(N + 1)]
		for i in range(1, N + 1):
			for s in range(1, K + 1):
				if arr[i - 1] <= s:
					dp[i][s] = dp[i - 1][s] or dp[i - 1][s - arr[i - 1]]
				else:
					dp[i][s] = dp[i - 1][s]
		return dp[N][K]