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

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

Use dynamic programming to solve this problem efficiently
Create a 2D array to store if a subset sum is possible for each element and target sum
Iterate through the array and update the 2D array based on current element and target sum
Check if the last element of the 2D array is true for the given target sum

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)