Subset Sum Equal To K Problem Statement

Given an array/list of positive integers and an integer K, determine if there exists a subset whose sum equals K.

Provide true if such a subset exists, otherwise return false.

Example:

Input:

ARR = {1,2,3,4}, K = 4

Output:

true

Explanation:

There exist subsets like {1,3} and {4} where the sum is 4, so the output is true.

Constraints:

1 ≤ T ≤ 5

1 ≤ N ≤ 10^3

0 ≤ ARR[i] ≤ 10^9

0 ≤ K ≤ 10^9

Time Limit: 1 sec

Question

Subset Sum Equal To K Problem Statement

Given an array/list of positive integers and an integer K, determine if there exists a subset whose sum equals K.

Provide true if such a subset exists, otherwise return false.

Example:

Input:

ARR = {1,2,3,4}, K = 4

Output:

true

Explanation:

There exist subsets like {1,3} and {4} where the sum is 4, so the output is true.

Constraints:

1 ≤ T ≤ 5
1 ≤ N ≤ 10^3
0 ≤ ARR[i] ≤ 10^9
0 ≤ K ≤ 10^9
Time Limit: 1 sec

Accepted Answer

def CheckForSequence(arr, n, k) :

# Traverse the array from end 
	# to start 
	for i in range(n - 1, -1, -1) :
		# if k is greater than 
		# arr[i] then subtract 
		# it from k 
		if (k >= arr[i]) :
			k = k - arr[i];

# If there is any subsequence 
	# whose sum is equal to k 
	if (k != 0) :
		return False; 
	else :
		return True;

# Driver code 
if __name__ == "__main__" :

A = [ 1, 2, 3, 4]; 
	n = len(A); 
	
	if (CheckForSequence(A, n, 4)) :
		print(True)
	else :
		print(False)