Answer to Question #218180 in Python for Krish

Question

Write a program k sum unique combinations

Answer 1

# subsequence whose sum is K
# Utility function to find the subsequences
# whose sum of the element is K
def subsetSumToK(arr, n, output, k):
	
	# Base Case
	if (n == 0):
		if (k == 0):
			output[0][0] = 0;
			return 1;
		else:
			return 0;
	
	# Array to store the subsequences
	# which includes the element arr[0]
	output1 = [[0 for j in range(50)] for i in range(1000)]
	
	# Array to store the subsequences
	# which not includes the element arr[0]
	output2 = [[0 for j in range(50)] for i in range(1000)]
	
	# Recursive call to find the subsequences
	# which includes the element arr[0]
	size1 = subsetSumToK(arr[1:], n - 1, output1, k - arr[0]);
	
	# Recursive call to find the subsequences
	# which not includes the element arr[0]
	size2 = subsetSumToK(arr[1:], n - 1, output2, k)
	
	# Loop to update the results of the
	# Recursive call of the function
	for i in range(size1):
		
		# Incremeing the length of
		# jagged array because it includes
		# the arr[0] element of the array
		output[i][0] = output1[i][0] + 1;
		
		# In the first column of the jagged
		# array put the arr[0] element
		output[i][1] = arr[0];
	
	# Loop to update the subsequence
	# in the output array
	for i in range(size1):
		for j in range(1, output1[i][0]+1):
			output[i][j + 1] = output1[i][j];
	
	# Loop to update the subsequences
	# which do not include the arr[0] element
	for i in range(size2):
		for j in range(output2[i][0] + 1):
			output[i + size1][j] = output2[i][j];
	
	return size1 + size2;


# Function to find the subsequences
# whose sum of the element is K
def countSubsequences(arr, n, output, k):
	size = subsetSumToK(arr, n, output, k);
	for i in range(size):	
		for j in range(1, output[i][0] + 1):
			print(output[i][j], end = ' ')
		print()
		
# Driver Code
if __name__=='__main__':


	print('Enter sequence: ')
	arr = list(map(int,input().split(' ')))
	length = len(arr)
	output = [[0 for j in range(50)] for i in range(1000)]
	print("k=")
	k=int(input())
	countSubsequences(arr, length, output, k);

#EXAMPLE TEST
#enter array:
#1 2 3
#k=3
#Output 
#1 2
#3
#(Unique subsequence (1+2)=3 and 3=3)